Максимальная сумма подмассива

Дан массив из $n$ целых чисел. Найдите наибольшую сумму непустого отрезка подряд идущих элементов (подмассива).

В первой строке $n$ ($1 \le n \le 2 \cdot 10^5$). Во второй — $n$ целых чисел ($|a_i| \le 10^9$).

Одно число — наибольшая сумма.

Сумма $[l, r]$ равна $p_r - p_{l-1}$. Для каждого $r$ лучшее $l$ — минимум предыдущих префиксов, значит ответ $\max_r (p_r - \min_{j < r} p_j)$. Это один проход за $O(n)$ (алгоритм Кадане — то же самое).

Подмассив должен быть непустым и при всех отрицательных числах: ответ — наибольший элемент, а не $0$. В примере $3 - 2 + 5 + 3 = 9$. Сумма достигает $2 \cdot 10^{14}$.

Источник: CSES, задача 1643.