Cho dãy \(A\) có \(N\) phần tử. Một đoạn con của dãy \(A\) là dãy các phần tử liên tiếp \(A_i, A_{i+1}, … A_j\) mà \(i \le j\). Tổng của đoạn con là \(A_i + A_{i+1} + … + A_j\).

Yêu cầu:

• Hãy tìm đoạn con có tổng lớn nhất.

Giới hạn:

• \(N \le 10^5\) và |\(A_i\)| \(\le 10^9\)

Dữ liệu vào:

• Dòng đầu tiên nhập vào số nguyên dương N.
• Dòng thứ hai, nhập vào N số nguyên, số thứ i là Ai

Kết quả:

• In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

Ví dụ: