Овај задатак је поновљен у циљу увежбавања различитих техника решавања.

Напиши програм који одређује највећи збир неког сегмента (подниза узастопних елемената) датог низа.

Улаз

Са стандардног улаза се уноси број \(n\) (\(1 \leq n \leq 50\,000\)), а затим \(n\) целих бројева између \(-10\) и \(10\), сваки број у посебном реду.

Излаз

На стандардни излаз испиши тражени збир.

Пример

Улаз

6
2
-3
4
-1
3
-2

Излаз

6

Сегмент највећег збира је \(4, -1, 3\).

Овај задатак има и другачија решења у делу збирке који следи.