tiếp có tổng lớn nhất (sae.*)

Cho số nguyên dương \(n\) và dãy số nguyên \(a_{1},\ a_{2},...,a_{n}\). Hãy tìm dãy con liên tiếp có tổng lớn nhất.

Dữ liệu vào:

+ Dòng đầu ghi số nguyên dương \(n\ (1 \leq n \leq 10^{6})\)

+ Dòng thứ 2 ghi \(n\) số nguyên lần lượt là \(a_{1},\ a_{2},...,a_{n}(\left| a_{i} \right| \leq 10^{9})\)

Kết quả:

Một số nguyên duy nhất là tổng của dãy con liên tiếp có tổng lớn nhất

Ví dụ:

Input	Output
5 1 -2 3 -1 4	6