Cho một dãy các số nguyên \(A\) có \(n\) phần tử, hãy tìm đoạn con không rỗng có tổng lớn nhất của dãy \(A\) này.

Mô tả đầu vào

• Dòng đầu chứa số \(N\).
• Dòng thứ \(2\) chứa \(N\) số, là miêu tả dãy \(A\).

Ràng buộc

• \(|A[i]| ≤ 10^9\)
• \(N ≤ 10^5\)

Mô tả đầu ra

Tổng của đoạn con có tổng lớn nhất tìm được.

6
1 2 3 -1 -1 -1

6