Cho số nguyên dương n và dãy số nguyên a1, a2, …, an.
Yêu cầu: Em hãy lập trình 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 tiên ghi số nguyên dương n (n ≤ 106).
+ Dòng thứ hai gồm n số nguyên a1, a2, …, an ghi cách nhau bởi một dấu cách (|ai| ≤ 103; i = 1, 2, …, n).
Kết quả: Ghi ra một số nguyên duy nhất là tổng lớn nhất tìm được.
Ví dụ:
|
Input |
Output |
|
10 1 3 -5 2 7 6 -2 4 -3 1 |
17 |
Giới hạn:
+ 50% số test có n ≤ 103.
+ 50% số test còn lại có n ≤ 106.