*23. Descreva um algoritmo em pseudocódigo para produzir a maior subseqüência crescente ou decrescente de uma seqüência de números inteiros distintos.
Passo 1
O enunciado pede que a gente construa um algoritmo em pseudocódigo que, dada uma sequência de
inteiros distintos, encontre a maior subsequência estritamente crescente ou a maior subsequência estritamente decrescente (isto é, aquela com mais elementos) e a retorne. O conteúdo principal aqui é programação dinâmica para Longest Increasing Subsequence (LIS) e Longest Decreasing Subsequence (LDS), além de uma rotina de reconstrução da solução.
Passo 2
Para usar programação dinâmica, vamos manter dois vetores de tamanho
:
tamanho da maior subsequência crescente que termina em
,
tamanho da maior subsequência decrescente que termina em
.
Também guardamos ponteiros e
para reconstruir as sequências.
Também guardamos ponteiros
Passo 3
Inicializamos para todo
:
,
,
,
.
Em seguida, para cada par de índices , atualizamos:
– se e
, então
e
;
– se e
, então
e
.
Em seguida, para cada par de índices
– se
– se
Passo 4
Depois de preencher os vetores, encontramos
Comparamos
e
e decidimos se vamos reconstruir a LIS ou a LDS.
Passo 5
A rotina de reconstrução começa do índice
final (ou seja,
ou
) e segue os ponteiros “prev” até
, empilhando os
numa lista que depois é invertida para dar a subsequência na ordem correta.
Resposta
Algorithm LargestMonotonicSubsequence(A[\(1\)\ldots n]):
for i \leftarrow \(1\) to n do
LISlen[i] \leftarrow \(1\)
LISprev[i] \leftarrow null
LDSlen[i] \leftarrow \(1\)
LDSprev[i] \leftarrow null
end for
for i \leftarrow \(1\) to n do
for j \leftarrow \(1\) to i-\(1\) do
if A[j] < A[i] and LISlen[j] \(+1\) > LISlen[i] then
LISlen[i] \leftarrow LISlen[j] \(+1\)
LISprev[i] \leftarrow j
end if
if A[j] > A[i] and LDSlen[j] \(+1\) > LDSlen[i] then
LDSlen[i] \leftarrow LDSlen[j] \(+1\)
LDSprev[i] \leftarrow j
end if
end for
end for
\(i_{\max\mathrm{LIS}}\) \leftarrow \(\arg\max_{1\le i \le n}\) LISlen[i]
\(i_{\max\mathrm{LDS}}\) \leftarrow \(\arg\max_{1\le i \le n}\) LDSlen[i]
if LISlen[\(i_{\max\mathrm{LIS}}\)] \(\geq\) LDSlen[\(i_{\max\mathrm{LDS}}\)] then
return Reconstruct(A, LISprev, \(i_{\max\mathrm{LIS}}\))
else
return Reconstruct(A, LDSprev, \(i_{\max\mathrm{LDS}}\))
end if
Procedure Reconstruct(A, prev, i):
S \leftarrow empty list
while i \(\neq\) null do
prepend A[i] to S
i \leftarrow prev[i]
end while
return S
Nesse pseudocódigo, a complexidade é
pelo duplo laço, e a memória adicional é
. A função retorna a subsequência crescente ou decrescente de maior comprimento.