Cho một dãy gồm n số nguyên a1, a2, …, an. Hãy tìm một đoạn con [dãy gồm các phần tử liên tiếp nhau] có tổng lớn nhất.
Dữ liệu vào:
- Dòng đầu ghi số n
- Dòng thứ hai ghi n số nguyên a1, a2, …, an, mỗi số có giá trị tuyệt đối không vượt quá 1000.
Kết quả:
Ghi ra 1 số là tổng lớn nhất tìm được.
Ví dụ:
Input
10
1 3 -5 2 7 6 -2 4 -3 1
Output
17
Giới hạn:
- 50% số test có n ≤ 103
- 50% số test còn lại có n ≤ 106
HƯỚNG DẪN
Cách tiếp cận đơn giản nhất ta tìm tổng từng đoạn và so sánh các kết quả này để tìm ra kết quả lớn nhất. Độ phức tạp cho cách này là O[n3], cách này chưa thể giải quyết cho bài toán trên.
Để cải tiến thuật toán trên, ta tính nhanh tổng của một đoạn bất kỳ bằng cách làm như sau:
- Gọi f[i] là tổng i phần tử đầu tiên, f[i] được tính như sau:
- f[0] = 0
- f[i] = f[i-1] + a[i]
- Tổng các phần tử từ i đến j là: f[j] – f[i-1]
Với cách cải tiến, độ phức tạp của thuật toán giảm từ O[n3] xuống còn O[n2] và ta có thể giải quyết được 50% số test của bài toán trên.
Để có thể giải quyết được 100% số test trên ta có 2 cách làm với độ phức tạp O[n] như sau:
Cách 1
Ta sử dụng biến sum để giữ giá trị tổng tiềm năng của các phần tử liên tục phía trước [khi thêm tổng này vào đoạn mới phía sau ta luôn nhận được một đoạn có tổng lớn hơn]. Ta nhận thấy khi giá trị của sum < 0 thì ta sẽ cập nhật lại giá trị sum = 0 [bỏ đi đoạn phía trước].
Đoạn code cho ý tưởng trên như sau:
int maxsum = 0;
int sum = 0;
for [int i = 1; i