Suma podniza karata
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 1 s | 256 Mb | standardni izlaz | standardni ulaz |
Đurica je pronašao n karata poređanih u niz. Na kartama su zapisani celi brojevi. Datom nizu karata A, Đurica dodeluje vrednost f(A) koja je jednaka sumi razlika vrednosti na uzastopnim kartama. Formalno,
f(A) = Σ(Ak + 1 - Ak), k = 1 .. n - 1
gde Ai predstavlja vrednost na i-toj karti u nizu.
Đurica iz niza želi da izbaci najviše K karata. Izbacivanjem nekih m karata, m ≤ K, dobija nov niz karata kojem ponovo računa vrednost na opisani način. Od svih mogućih odabira vrednosti m i svih mogućih odabira m karata koje će izbaciti, njega zanima onaj niz karata koji će imati najveću vrednost. Pomozite Đurici i recite mu koliko je ta najveća vrednost. Primetimo da Đurica ni u jednom momentu ne menja raspored karata datih na početku.
U prvom redu nalaze se celi brojevi N i K. U narednom redu se učitavaju celi brojevi Ai, odvojeni jednim znakom razmaka.
U prvom i jedinom redu ispisati jedan ceo broj koji predstavlja najveću vrednost niza koju Đurica može da dobije od početnog izbacivanjem najviše K karata.
2 ≤ N ≤ 500.000
0 ≤ K ≤ N - 2
-1.000.000 ≤ Ai ≤ 1.000.000
11 4
1 7 2 5 3 8 2 3 6 5 5
5
Jedno optimalno rešenje je da se izbacimo 3 karte iz niza. Karte koje treba izbaciti imaju na sebi vrednost 5.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.