Самый выгодный отрезок

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

Числа могут быть отрицательными, поэтому взять весь ряд не всегда выгодно.

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n$ чисел от $-10^9$ до $10^9$.

Одно число.

Состояние — «наибольшая сумма куска, заканчивающегося ровно на позиции $i$». Такой кусок либо продолжает предыдущий, либо начинается заново. Ответ — наибольшее из состояний, а не последнее.