Se citesc n preturi ale unei actiuni, cate unul pentru fiecare din n zile consecutive. Determinati, folosind Programarea Dinamica, profitul maxim ce se poate obtine cumparand actiunea intr-o zi si vanzand-o intr-o zi ulterioara (o singura tranzactie completa). Daca nu se poate obtine niciun profit, afisati 0.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n preturi.
- Date de iesire
- Se afiseaza un singur numar: profitul maxim posibil (sau 0 daca nu exista profit).
- Restrictii
- 1 <= n <= 100000, 0 <= pret <= 10^9
Exemple
Exemplul 1
Intrare
6 7 1 5 3 6 4
Iesire
5
Exemplul 2
Intrare
5 7 6 4 3 1
Iesire
0