Сечење#10961

Сечење

0,5 секунди

512 мегабајтова

Врло лако

Problem Statement

Imate niz $a$ koji se sastoji od $n$ celih brojeva. Vaš zadatak je da pronađete podniz (kontinuirani deo niza) koji ima najveći mogući zbir.

Podniz niza $a$ je niz koji se može dobiti iz $a$ brisanjem nekih (možda nijednog) elemenata sa početka i nekih (možda nijednog) elemenata sa kraja.

Na primer, ako je niz $a = [3, - 2, 5, - 1]$ a = [3, -2, 5, -1], podniz sa najvećim mogućim zbirom je $[3, - 2, 5]$ [3, -2, 5], čiji je zbir $6$ .

Ulaz

Prvi red sadrži jedan ceo broj $n$ $(1 \leq n \leq 1 0^{5})$ (1 \leq n \leq 10^5) — dužinu niza.
Drugi red sadrži $n$ celih brojeva $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) — elemente niza.

Izlaz

Примери

Пример 1

Loading

a = [3, - 2, 5, - 1]

[3, - 2, 5]

(1 \leq n \leq 1 0^{5})

a_{1}, a_{2}, \dots, a_{n}

(- 1 0^{4} \leq a_{i} \leq 1 0^{4})