Subseqüència de suma màxima P92712

Statement

Donada una seqüència de $n$ enters $x_1, \dots x_n$ , es vol trobar el valor màxim de $\sum_{k=i}^j x_k$ per a $1\le i\le n$ i $1\le j\le n$ . Fixeu-vos que quan tots els $x_i$ són negatius el màxim és zero, corresponent al sumatori buit.

Entrada

L’entrada consisteix en diversos casos, cadascun compost per un nombre $n$ seguit dels $n$ enters $x_1, \dots, x_n$ .

Sortida

Per a cada cas, escriviu el valor màxim de totes les subseqüències consecutives.

Public test cases

Input

6   -2 11 -4 13 -5 -2
3   1 2 3
1   -1
0
3   0 0 0
11  -90 1 0 2 0 0 -90 2 1 0 -300
5   100 -1 123 1 -42
2   1 1728

Output

Information

Author: Enric Sànchez Cusell
Language: Catalan
Official solutions: C++
User solutions: C++