Maximum subarray sum

You are given an array of $n$ integers. Find the maximum sum of a non-empty block of consecutive elements (a subarray).

The first line contains $n$ ($1 \le n \le 2 \cdot 10^5$). The second line contains $n$ integers ($|a_i| \le 10^9$).

A single number — the maximum sum.

The sum of $[l, r]$ is $p_r - p_{l-1}$. For every $r$ the best $l$ is the minimum of the earlier prefixes, so the answer is $\max_r (p_r - \min_{j < r} p_j)$. This is one pass, $O(n)$ (Kadane's algorithm is the same idea).

The subarray must be non-empty even when all numbers are negative: the answer is then the largest element, not $0$. In the example $3 - 2 + 5 + 3 = 9$. The sum reaches $2 \cdot 10^{14}$.

Source: CSES, problem 1643.