Se citesc n numere naturale. Determinati, folosind Programarea Dinamica, suma maxima a elementelor unui subsir CRESCATOR al sirului (nu neaparat cel mai lung, ci cel cu suma maxima).
- 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 unui subsir crescator.
- Restrictii
- 1 <= n <= 1000, 0 <= element <= 10^6
Exemple
Exemplul 1
Intrare
5 1 101 2 3 100
Iesire
106
Exemplul 2
Intrare
1 5
Iesire
5