Шахтарі#10952

Шахтарі

0,8 секунди

256 мегабайтів

Середня

Дано масив цілих чисел. Ваше завдання — знайти підмасив з максимально можливою сумою. Підмасив повинен містити принаймні один елемент.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1 \leq n \leq 1 0^{5})$ (1 \leq n \leq 10^5) — кількість елементів у масиві.
Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(- 1 0^{4} \leq a_{i} \leq 1 0^{4})$ (-10^4 \leq a_i \leq 10^4) — елементи масиву.

5
-2 1 -3 4 -1

Приклад 1

У наведеному прикладі підмасив з максимальною сумою — це $[4]$ , який має суму $4$ .