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

Cho dãy gồm n số nguyên a1,a2,…,a_n.

Yêu cầu: Hãy tìm dãy con gồm các phần tử liên tiếp nhau có tổng các phần tử lớn nhất.

Dữ liệu vào: Từ tệp văn bản SUMMAX.INP gồm:

• Dòng đầu tiên gồm một số nguyên dương n.

• Dòng tiếp theo ghi dãy số a1,a2,…,a_n. Mỗi số có giá trị tuyệt đối không vượt quá 107.

Kết quả: Ghi vào tệp văn bản SUMMAX.OUT một số nguyên duy nhất tổng lớn nhất của dãy con tìm được.

Ví dụ:

SUMMAX.INP

5
1 2 3 -2 5

SUMMAX.OUT

9

SUMMAX.INP

4
-1 -2 -3 -4

SUMMAX.OUT

-1

Giới hạn

Có 50% số test có n≤1000

Có 50% số test có n≤10^6