Bài 2. (5 điểm) Dãy con có tổng lớn nhất

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

Yêu cầu: Cho dãy số nguyên a₁, a₂, .., 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₁, a₂, .., a_N (|a_i| ≤ 10⁶, i=1..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ụ:

TONGMAX.INP                                         TONGMAX.OUT

6                                                                18

3 8 -2 4 5 -1

Giới hạn:

• Có 12/25 test có n≤200, tương ứng 2,4 điểm;
• Có 8/25 test có 200<n≤1000, tương ứng 1,6 điểm;
• Có 5/25 test có 1000<N≤1000000, tương ứng 1,0 điểm

ngôn ngữ c++