Cho số nguyên dương \(n\) và dãy số nguyên \(a_1, a_2,..., a_n.\)

Yêu cầu: Hãy viết chương trình in ra tổng lớn nhất của dãy con liên tiếp từ dãy đã cho.

Ví dụ: cho \(n=9\) và dãy \(A=[-2, 1, -3, 4, -1, 2, 1, -5, 4]\). Tổng lớn nhất là \(6\) đó là dãy con: \([4, -1, 2, 1].\)

Input:

• Dòng đầu chứa số nguyên dương \(n;\)
• Dòng thứ hai chứa n số nguyên \(a_1, a_2,…,a_n (|a_i|≤ 10^6)\).

Output:

• Gồm một số nguyên duy nhất là kết quả cần tìm.

Ví dụ:

Input:

9
-2 1 -3  4  -1 2 1 -5 4

Output:

6

Ràng buộc:

• Có 50% test ứng 50% số điểm của bài với \(n ≤ 20;\)
• Có 50% test khác ứng với 50% số điểm còn lại của bài với \(n ≤ 10^6.\)