Bài 2

Sau $n$ bài kiểm tra, điểm của Dũng được ghi lại thành dãy số nguyên $a_1, a_2, \ldots, a_n$. Điểm này có thể âm (tương ứng với điểm phạt) nếu như lần kiểm tra đó Dũng gian lận hoặc sử dụng chat GPT. Thầy giáo muốn biết “giai đoạn tiến bộ nhất” mà Dũng thực hiện được, giai đoạn này là dãy các bài kiểm tra liên tiếp của Dũng có tổng điểm lớn nhất.

Yêu cầu: Hãy xác định tổng điểm của “giai đoạn tiến bộ nhất” mà Dũng thực hiện được.

Nhập từ bàn phím

• Dòng đầu tiên chứa số nguyên dương $n$ $(1 \le n \le 10^6)$.
• Dòng thứ hai chứa $n$ số nguyên lần lượt là $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9\ \forall i = 1, 2, \ldots, n)$. Hai số liên tiếp cách nhau bằng khoảng trống (space).

In ra màn hình một số nguyên duy nhất là kết quả tìm được.

• Có $50\%$ số tests ứng với $50\%$ số điểm của bài có $n \le 500$.
• $30\%$ số tests tiếp theo ứng với $30\%$ số điểm của bài có $n \le 5000$.
• Các tests còn lại không có ràng buộc bổ sung.