Збир и производ

Problem Statement

Date je niz celih brojeva a_1, a_2, \ldots, a_n. Vaš zadatak je da pronađete podniz sa najvećim mogućim zbirom. Podniz je definisan kao niz elemenata koji se pojavljuju uzastopno u originalnom nizu. Na primer, ako je dati niz a = [-2, 1, -3, 4, -1, 2, 1, -5, 4], podniz sa najvećim zbirom je [4, -1, 2, 1], čiji je zbir $6$.

Ulaz

• Prvi red sadrži jedan ceo broj $n$ (1 \leq n \leq 10^5), koji predstavlja broj elemenata u nizu.

• Drugi red sadrži $n$ celih brojeva a_1, a_2, \ldots, a_n (-10^4 \leq a_i \leq 10^4), koji predstavljaju elemente niza.

Izlaz

• Ispisati jedan ceo broj, koji predstavlja najveći mogući zbir podniza.

Primer

Ulaz:

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

Izlaz:

6

U ovom primeru, podniz sa najvećim zbirom je [4, -1, 2, 1], čiji je zbir $6$.