Se citesc n preturi ale unei actiuni (cate unul pentru fiecare din n zile) si un numar natural k. O tranzactie consta intr-o cumparare urmata de o vanzare; nu puteti detine mai mult de o actiune simultan (trebuie sa vindeti inainte de a cumpara din nou). Determinati, folosind Programarea Dinamica, profitul maxim ce se poate obtine facand CEL MULT k tranzactii.
- Date de intrare
- Pe prima linie se citesc n si k. Pe a doua linie se citesc cele n preturi.
- Date de iesire
- Se afiseaza un singur numar: profitul maxim posibil.
- Restrictii
- 1 <= n <= 1000, 1 <= k <= 100, 0 <= pret <= 10^9
Exemple
Exemplul 1
Intrare
6 2 3 2 6 5 0 3
Iesire
7
Exemplul 2
Intrare
5 2 1 2 3 4 5
Iesire
4