Лучший подотрезок

Дан список из $n$ чисел. Рассмотрите все непустые куски из подряд идущих элементов.

Найдите наибольшую сумму такого куска.

В первой строке число $n$ от $1$ до $2 \cdot 10^5$. Во второй — $n$ целых чисел от $-10^9$ до $10^9$ через пробел.

Одно число.

Кусков около $n^2$, перебрать их нельзя. Подумайте, что достаточно знать про лучший кусок, кончающийся в текущей позиции: он либо продолжает предыдущий, либо начинается заново.