Encontre uma subseqüência crescente de extensão máxima e uma subseqüência decrescente de extensão máxima a partir da seqüência
.
Passo 1
O enunciado dá a sequência
e pede (a) uma subsequência estritamente crescente de comprimento máximo (LIS) e (b) uma subsequência estritamente decrescente de comprimento máximo (LDS). Vamos usar programação dinâmica para calcular os dois casos.
Passo 2
Definimos para cada posição
o valor
sendo
se não houver
com
. Aqui
é o
-ésimo elemento da sequência. Esse cálculo nos dá o comprimento da LIS terminando em
.
Passo 3
Calculando
para
em
:
O máximo é
.
Passo 4
Para reconstruir uma LIS de comprimento 5, escolhemos o índice
tal que
. Um deles é
(
). Voltamos empilhando predecessores que satisfazem
e
:
índices correspondem aos valores
índices
Passo 5
Para a LDS, definimos
com
se não houver
com
. Esse é o comprimento da LDS terminando em
.
Passo 6
Calculando
para
na mesma sequência:
O máximo é
.
Passo 7
Para reconstruir uma LDS de comprimento 3, tomou-se
(
). Seus predecessores são índices
e
, pois
e
,
,
. Isso dá
Resposta
A subsequência crescente de extensão máxima tem comprimento 5, por exemplo
A subsequência decrescente de extensão máxima tem comprimento 3, por exemplo