Dãy con thịnh vượng

Xét dãy số nguyên gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Một dãy con liên tiếp của dãy $a_1, a_2, \dots, a_n$ là dãy số nguyên có dạng $a_i, a_{i+1}, \dots, a_j$ ($1 \le i \le j \le n$).
Một dãy con liên tiếp được gọi là dãy con thịnh vượng nếu tổng của các phần tử trong dãy con liên tiếp đó là lớn nhất trong tất cả các dãy con liên tiếp.

Yêu cầu: Cho trước một dãy số nguyên $a_1, a_2, \dots, a_n$. Hãy tìm tổng của một dãy con thịnh vượng của dãy đã cho.

Ví dụ: Cho dãy $5, -3, 7, -9$. Một dãy con thịnh vượng có các phần tử là $5, -3, 7$. Khi đó, tổng của dãy con thịnh vượng là $S = 5 - 3 + 7 = 9$ là tổng các phần tử liên tiếp lớn nhất.

Từ tệp văn bản DAYCON.INP gồm:

• Dòng đầu tiên chứa số nguyên dương $n$ ($1 \le n \le 10^6$)
• Dòng thứ 2 chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^9$), các số trên cùng dòng viết cách nhau một dấu cách.

Ghi ra tệp văn bản DAYCON.OUT một số duy nhất là tổng các phần tử của dãy con thịnh vượng của dãy đã cho.

• Có 50% số test tương ứng với 50% số điểm của bài có $n \le 100$
• Có 30% số test tương ứng với 30% số điểm của bài có $n \le 5000$
• Có 20% số test tương ứng với 20% số điểm của bài có $n \le 10^6$