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 22,5,7,2,23,10,15,21,3,17.

Passo 1

O enunciado dá a sequência
22,\,5,\,7,\,2,\,23,\,10,\,15,\,21,\,3,\,17
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 i o valor
L_i = 1 + \max_{\substack{j<i\a_j<a_i}} L_j,
sendo L_i=1 se não houver j<i com a_j<a_i. Aqui a_i é o i-ésimo elemento da sequência. Esse cálculo nos dá o comprimento da LIS terminando em a_i.

Passo 3

Calculando L_i para i=1,\dots,10 em
(a_1,\dots,a_{10})=(22,5,7,2,23,10,15,21,3,17):
L_1=1
L_2=1
L_3=2
L_4=1
L_5=3
L_6=3
L_7=4
L_8=5
L_9=2
L_{10}=5
O máximo é \max_i L_i=5.

Passo 4

Para reconstruir uma LIS de comprimento 5, escolhemos o índice i tal que L_i=5. Um deles é i=8 ( a_8=21). Voltamos empilhando predecessores que satisfazem a_j<a_i e L_j=L_i-1:
índices 2\to3\to6\to7\to8 correspondem aos valores
5,\;7,\;10,\;15,\;21.

Passo 5

Para a LDS, definimos
D_i = 1 + \max_{\substack{j<i\a_j>a_i}} D_j,
com D_i=1 se não houver j<i com a_j>a_i. Esse é o comprimento da LDS terminando em a_i.

Passo 6

Calculando D_i para i=1,\dots,10 na mesma sequência:
D_1=1
D_2=2
D_3=2
D_4=3
D_5=1
D_6=2
D_7=2
D_8=2
D_9=3
D_{10}=3
O máximo é \max_i D_i=3.

Passo 7

Para reconstruir uma LDS de comprimento 3, tomou-se i=4 ( a_4=2). Seus predecessores são índices 1 e 2, pois 22>5>2 e D_1=1, D_2=2, D_4=3. Isso dá
22,\;5,\;2.

Resposta

A subsequência crescente de extensão máxima tem comprimento 5, por exemplo
5,\,7,\,10,\,15,\,21.
A subsequência decrescente de extensão máxima tem comprimento 3, por exemplo
22,\,5,\,2.

Exercícios relacionados