Миньори

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

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

Вход

• Първият ред съдържа едно цяло число $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$.