Купчини

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

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

Вход

• Първият ред съдържа едно цяло число n (1 ≤ n ≤ 10^5) — дължината на масива.

• Вторият ред съдържа n цели числа A[i] (-10^9 ≤ A[i] ≤ 10^9) — елементите на масива.

Изход

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

Пример

Вход

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

Изход

6

Забележка

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