Кролик#10956

Кролик

0,1 секунди

256 мегабайтів

Дуже складна

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

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100000) — кількість елементів у масиві.

Другий рядок містить $n$ цілих чисел $A_{i}$ A_i ( $- 1 0^{9} \leq A_{i} \leq 1 0^{9}$ -10^9 \leq A_i \leq 10^9) — елементи масиву.

Вихідні дані

Виведіть одне ціле число — максимальну суму підмасиву масиву $A$ .

Приклади

Приклад

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

Приклад 1

Примітка

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