Seqüències quasi-creixents P51901


Statement
 

pdf   zip

thehtml

En aquest problema, direm que una seqüència de naturals x1, x2, …, xn és quasi-creixent si per a tot i∈{1,…,n−2}, xi < xi+1 o bé xi < xi+2 (o ambdues condicions). Per exemple, la seqüència 1 1 2 3 2 4 1 és quasi-creixent. Fixeu-vos que una seqüència amb dos o menys elements sempre és quasi-creixent. Per a cada seqüència donada, calculeu la llargada de la subseqüència quasi-creixent més llarga.

Entrada

L’entrada consisteix en diverses seqüències de naturals. Cada seqüència està precedida per la seva llargada, la qual és com a mínim dos. La darrera seqüència és de llargada zero, i no s’ha de processar.

Sortida

Escriviu la llargada de la subseqüència quasi-creixent més llarga de cada seqüència donada.

Observació

No podeu usar strings, ni vectors o similars.

Public test cases

  • Input

    7   1 1 2 3 2 4 1
5   1 2 3 4 5
14  0 0 1 0 2 0 2 0 3 0 4 5 1 1
5   0 0 0 0 0
2   100 99
6   0 0 1 0 0 1
3   1 2 3
3   3 2 1
0

    Output

    7
5
8
2
2
4
3
2
    • Information
    Author
    Àlvar Vinacua
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++