Seqüències quasi-creixents P51901


Statement
 

pdf   zip

html

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++