Лепо

Problem Statement

U datom nizu brojeva, vaš zadatak je da pronađete podniz sa najvećim mogućim zbirom. Podniz mora sadržati najmanje jedan element.

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

• Ispišite jedan ceo broj, koji predstavlja najveći mogući zbir podniza.

Primer

Ulaz

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

Izlaz

6

Objašnjenje

U datom primeru, podniz sa najvećim zbirom je [4, -1, 2, 1], čiji zbir iznosi ( 6 ).