Bài 4. Dãy con có tổng lớn nhất

Cho dãy số nguyên ~a_1, a_2, \dots, a_N~. Một dãy con liên tiếp có dạng ~a_i, a_{i+1}, \dots, a_j~ với ~1 \leq i \leq j \leq N~, tổng của dãy con liên tiếp ~a_i, a_{i+1}, \dots, a_j~ là ~a_i + a_{i+1} + \dots + a_j~.

Yêu cầu: Cho dãy số nguyên ~a_1, a_2, \dots, a_N~, tìm dãy con liên tiếp có tổng lớn nhất.

Dữ liệu:

Vào từ tệp văn bản TONGMAX.INP gồm:

• Dòng 1: ghi số nguyên dương ~N~.
• Dòng 2: ghi lần lượt các số nguyên ~a_1, a_2, \dots, a_N~ (~|a_i| \leq 10^6~, với ~i = 1 \dots N~).

Kết quả: ghi ra tệp văn bản TONGMAX.OUT gồm một số duy nhất là tổng của dãy con tìm được.

Ví dụ:

Dữ liệu đầu vào (TONGMAX.INP):

6
3 8 -2 4 5 -1

Dữ liệu đầu ra (TONGMAX.OUT):

18

Giới hạn:

• Subtask 1: Có 40% số điểm với ~N \leq 100~
• Subtask 2: Có 40% số điểm với ~N \leq 1000~
• Subtask 3: Có 20% số điểm với ~N \leq 10^6~