| Fişierul intrare/ieşire: | palalila2.in, palalila2.out | Sursă | FMI No Stress 2010 |
| Autor | Vlad Duta | Adăugată de |  Dumitran Adrian Marius •marius135 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | palalila2.out |
|---|---|
| nostressATfmi | 7 |
Explicaţie
Un posibil subsir zig-zag de lungime 7 este osesAmi
