Xét dãy các số nguyên gồm n phần tử a₁, a₂, ..., a_n. Một dãy con liên tiếp của dãy
 a₁, a₂, ..., a_n là dãy số nguyên có dạng a_i, a_i+1, a_i+2, ..., a_j (1≤ i ≤ j ≤ n).

Yêu cầu: Cho trước dãy các số nguyên a₁, a₂, ..., a_n. Hãy tìm một dãy con liên tiếp của dãy đã cho có tổng các phần tử đạt lớn nhất.

Ví dụ: Cho dãy 5, -3, 7, -9. Một dãy con liên tiếp của dãy này có tổng các phần tử đạt lớn nhất là dãy 5, -3, 7. Khi đó, tổng lớn nhất là S = 5 - 3 + 7 = 9.

Dữ liệu: gồm 2 dòng:

• Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 10⁶);
• Dòng thứ hai chứa n số nguyên, số thứ i là a_i (|a_i| ≤ 10⁶). Các số trên cùng dòng viết cách nhau một dấu cách.

Kết quả:

một số duy nhất là tổng các phần tử của dãy con liên tiếp đạt lớn nhất.