Субпоследователности със същата сума

Задача: Сума на подмасив

Даден е масив от цели числа с дължина ( n ). Вашата задача е да намерите подмасив с максимална сума. Подмасивът трябва да съдържа поне един елемент.

Вход

• Първият ред съдържа едно цяло число ( n ) ((1 \leq n \leq 10^5)), което представлява броя на елементите в масива.

• Вторият ред съдържа ( n ) цели числа ( a_1, a_2, \ldots, a_n ) ((-10^4 \leq a_i \leq 10^4)), които представляват елементите на масива.

Изход

• Изведете едно цяло число — максималната сума на подмасив от дадения масив.

Пример

Вход

5
-2 1 -3 4 -1 2 1 -5 4

Изход

6

Забележка

В примера по-горе, подмасивът с максимална сума е [4, -1, 2, 1], който има сума 6.