Bài tập về dãy con và đoạn con

#1

Cho một dãy số, tìm:

  • Dãy con khác rỗng có tổng lớn nhất
  • Đoạn con khác rỗng có tổng lớn nhất

Dữ liệu vào

  • Gồm nhiều test, dòng đầu tiên là số lượng test T (1 ≤ T ≤ 10)
  • Mỗi bộ test gồm hai dòng:
    • Dòng đầu gồm số lượng phần tử của dãy N (1 ≤ N ≤ 100000)
    • Dòng tiếp theo gồm N số nguyên trong khoảng [-10^4, 10^4]

Input #1

2

4
1 2 3 4

6
2 -1 2 3 4 -5

Output #1

10 10
11 10
mn giúp mình giải bài này với

#2

Dãy con thì lấy tổng các số dương thôi chứ sao :smiley:

Còn đoạn con thì do tính liên tục nên bạn tính luôn tổng chạy và drop nó nếu là số âm.

3 Likes
#3

6
2 -1 2 3 4 -5
bạn code tay cho mình ví dụ này đc k

#5 
int result = -10000;
for (int i = 0; i < n; i ++) {
	for (int j = i; j < n; j ++) {
		int sum = 0;
		for (int k = i; k <= j; k ++) {
			sum += arr[k];
		}
		result = max(result, sum);
	}
}

có thể sẽ timeout nếu N = 100000

#7

như này thì dùng prefix sum cho nhanh b

6
2 -1 2 3 4 -5
b phân tích giúp m đoạn con gồm gtri nào , dãy con gồm gtri nào là đc

#8

dãy con là 2 -1 2 3 4

#9

max_ending_here: 2 1 3 6 10 5
vậy max = 10

2 Likes
#12

còn đoạn con là từ đâu đến đâu

#13

b có code ko cho mình tham khảo với ạ

#14

Bác tham khảo hướng dẫn này:


Và hướng dân này:
https://e16cn-ptit.blogspot.com/2017/12/p171sume-round-1e-day-con-co-tong-lon.html

1 Like
#15

As requested

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?