apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

lindambr Lineārā dambrete 1 sek.


 Uzdevums

"Lineārā dambrete" ir galda spēle, kuru spēlē uz 1*N lauciņu liela laukuma. Atšķirībā no parastās dambretes, visi kauliņi ir vienā krāsā, bet tie var būt dažādi augsti. Situāciju uz spēles laukuma katrā brīdī raksturo N veselu skaitļu virkne a1,a2, ..., aN, kur ai - norāda i-tajā lauciņā esošā kauliņa augstumu (ja lauciņš ir tukšs, tad ai=0).

No lauciņa i var izdarīt gājienu uz lauciņu k tikai tad, ja i<k un visi kauliņi lauciņos i+1,...,k ir zemāki par kauliņu lauciņā i (lauciņš k var nebūt tukšs). Starpību i-k nosauksim par gājiena no i uz k garumu.

Uzrakstiet programmu, kas dotajai spēles situācijai aprēķina lielāko iespējamo gājiena garumu!

 
 Ievaddati

Teksta faila lindambr.dat pirmajā rindā dots spēles laukuma garums N (1 ≤N≤100000). Faila otrajā rindā doti N veseli nenegatīvi skaitļi: a1,a2 , ..., aN - spēles laukuma apraksts. Starp katriem diviem blakus skaitļiem ir viens tukšumsimbols. Zināms, ka visiem i (1≤i≤N) ai vērtība nepārsniedz 100000.

 
 Izvaddati

Teksta faila lindambr.rez vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - lielākais iespējamais gājiena garums.

 
 Piemērs

lindambr.datlindambr.rez
5
1 4 2 3 5
2

 
 Atsauces
Uzdevums izmantots Igaunijas informātikas olimpiādē 2004.gadā
Autors: Ahto Truu

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS