Subseqüència de suma màxima P92712


Statement
 

pdf   zip

thehtml

Donada una seqüència de n enters x1, … xn, es vol trobar el valor màxim de ∑k=ij xk per a 1≤ i≤ n i 1≤ j≤ n. Fixeu-vos que quan tots els xi 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 x1, …, xn.

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

    20
6
0
0
0
3
223
1729
    • Information
    Author
    Enric Sànchez Cusell
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++