Зид

Problem Statement

U datom nizu celih brojeva, vaš zadatak je da pronađete podniz sa najvećim mogućim zbirom. Podniz mora sadržati najmanje jedan element, a zbir podniza je suma elemenata unutar njega.

Na primer, za niz [-2,1,-3,4,-1,2,1,-5,4], podniz sa najvećim zbirom je [4,-1,2,1], sa zbirom 6.

Ulaz

• Prva linija sadrži jedan ceo broj n (1 ≤ n ≤ 10^5), koji predstavlja broj elemenata u nizu.

• Druga linija sadrži n celih brojeva, koji predstavljaju elemente niza. Svaki broj je u opsegu od -10^4 do 10^4.

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

Napomena

U datom primeru, podniz [4,-1,2,1] daje najveći zbir 6.