P1115 Maximum Subarray Sum

Given a sequence $a$ of length $n$, choose a non-empty contiguous subarray whose sum is maximized.

The first line contains an integer $n$, the length of the sequence. The second line contains $n$ integers; the $i$-th is $a_i$.

Output one line with a single integer, the answer.

- Explanation for Sample 1: Choose the subarray $[3, 5]$, which is $\{3, -1, 2\}$; its sum is $4$. - Constraints: - For 40% of the testdata, it is guaranteed that $n \le 2 \times 10^3$. - For 100% of the testdata, it is guaranteed that $1 \le n \le 2 \times 10^5$ and $-10^4 \le a_i \le 10^4$. Translated by ChatGPT 5