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ụ: