Tổng đoạn con lớn nhất (Maximum Subarray Sum)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $n$ số nguyên. Hãy tìm tổng lớn nhất có thể của một đoạn con liên tiếp không rỗng.

Nếu chọn đoạn $[l,r]$, giá trị của đoạn là

Các phần tử có thể âm, vì vậy đoạn tối ưu không nhất thiết là toàn bộ mảng.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In tổng lớn nhất của một đoạn con liên tiếp không rỗng.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le2\cdot10^5$

• $-10^9\le x_i\le10^9$

• Đoạn con phải không rỗng.

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: Mọi phần tử đều không âm: $a_i\ge0$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

8
-1 3 -2 5 3 -5 2 2

Output

9

Giải thích

Với dãy

đoạn từ vị trí $2$ đến vị trí $5$ có tổng

Không có đoạn liên tiếp nào có tổng lớn hơn $9$, nên kết quả là $9$.