Заек

Задача: Изчисляване на максимална сума на подмасив

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

Вход

• Първият ред съдържа едно цяло число n (1 ≤ n ≤ 100,000) — броят на елементите в масива.

• Вторият ред съдържа 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.