Fişierul intrare/ieşire:palalila2.in, palalila2.outSursăFMI No Stress 2010
AutorVlad DutaAdăugată demarius135Dumitran Adrian Marius marius135
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Palalila2

Fie un sir S format din litere mari si mici ale alfabetului englez. Un subsir al lui S este un sir format din caractere (nu neaparat consecutive) ale acestuia, in ordinea in care apar. Numim subsir zig-zag un subsir S' = (s1, s2, ..., sn) al lui S pentru care s1<s2, s2>s3, s3<s4, s4>s5, ... unde prin < si > intelegem mai mic, respectiv mai mare lexicografic (Stim ca 'A'<'B'<...<'Z'<'a'<...<'z').
Determinati lungimea maxima a unui subsir zig-zag al lui S.

Date de intrare

Fişierul de intrare palalila2.in va contine o singura linie pe care se va afla sirul S.

Date de ieşire

În fişierul de ieşire palalila2.out se va afisa pe prima linie lungimea determinata pentru cel mai lung subsir zig-zag al lui S.

Restricţii

  • 1 ≤ lungimea sirului S ≤ 500 000
  • Pentru 50% din teste 1 ≤ lungimea sirului S ≤ 4 000

Exemplu

palalila2.inpalalila2.out
nostressATfmi
7

Explicaţie

Un posibil subsir zig-zag de lungime 7 este osesAmi

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content