*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 n 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 n:
\text{LISlen}[\,i\,] = tamanho da maior subsequência crescente que termina em A[i],
\text{LDSlen}[\,i\,] = tamanho da maior subsequência decrescente que termina em A[i].
Também guardamos ponteiros \text{LISprev}[\,i\,] e \text{LDSprev}[\,i\,] para reconstruir as sequências.

Passo 3

Inicializamos para todo i\in\{1,\dots,n\}:
\text{LISlen}[i]\gets 1, \text{LISprev}[i]\gets \text{null},
\text{LDSlen}[i]\gets 1, \text{LDSprev}[i]\gets \text{null}.
Em seguida, para cada par de índices 1\le j<i\le n, atualizamos:
– se A[j]<A[i] e \text{LISlen}[j]+1>\text{LISlen}[i], então
\text{LISlen}[i]\gets\text{LISlen}[j]+1 e \text{LISprev}[i]\gets j;
– se A[j]>A[i] e \text{LDSlen}[j]+1>\text{LDSlen}[i], então
\text{LDSlen}[i]\gets\text{LDSlen}[j]+1 e \text{LDSprev}[i]\gets j.

Passo 4

Depois de preencher os vetores, encontramos
i_{\text{maxLIS}} = \arg\max_{1\le i\le n}\text{LISlen}[i],\quad i_{\text{maxLDS}} = \arg\max_{1\le i\le n}\text{LDSlen}[i].
Comparamos \text{LISlen}[\,i_{\text{maxLIS}}\,] e \text{LDSlen}[\,i_{\text{maxLDS}}\,] e decidimos se vamos reconstruir a LIS ou a LDS.

Passo 5

A rotina de reconstrução começa do índice i final (ou seja, i_{\text{maxLIS}} ou i_{\text{maxLDS}}) e segue os ponteiros “prev” até \text{null}, empilhando os A[i] 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 é O(n^2) pelo duplo laço, e a memória adicional é O(n). A função retorna a subsequência crescente ou decrescente de maior comprimento.

Exercícios relacionados