Se citesc n numere intregi. Determinati, folosind Programarea Dinamica, suma maxima a unei subsecvente NEVIDE de elemente CONSECUTIVE (algoritmul lui Kadane).
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n numere.
- Date de iesire
- Se afiseaza un singur numar: suma maxima a unei subsecvente consecutive.
- Restrictii
- 1 <= n <= 100000, -10^9 <= element <= 10^9
Exemple
Exemplul 1
Intrare
5 -2 1 -3 4 -1
Iesire
4
Exemplul 2
Intrare
1 -5
Iesire
-5