Análise de Algoritmos | Aulas | Dicionário | Índice

Subsequência crescente máxima

O problema da subsequência crescente máxima e suas variações está por trás de várias questões computacionais básicas da ciência e da engenharia. A resolução do problema é uma boa introdução ao método de programação dinâmica.

Esta página é inspirada na seção 15.4 de livro CLRS, que trata do problema conhecido como LCS (= longest common subsequence) problem.

O problema

Seja que A[1 .. n] é uma sequência de números. (Nesta página, uma sequência é o mesmo que um vetor.) Uma subsequência de A[1 .. n] é o que sobra depois que um conjunto arbitrário de elementos da sequência é apagado. Para melhor entender as sutilezas do conceito, convém dar uma definição mais formal.

Uma sequência S[1 .. k] é subsequência de uma sequência A[1 .. n] se existe uma injeção de S em A. Uma injeção de S em A é um sequência (i₁, i₂, … , i_k) de índices tal que  1 ≤ i₁ < i₂ < ⋯ < i_k ≤ n  e

S[1] = A[i₁], S[2] = A[i₂], … , S[k] = A[i_k] .

Dizemos que o índice 1 de S casa com o índice i₁ de A, que o índice 2 de S casa com o índice i₂ de A, etc. De maneira mais geral, dizemos que um índice j de S casa com um índice m de A se existe uma injeção (i₁, i₂, … , i_k) tal que  i_j = m. 

Uma subsequência S[1 .. k] de A[1 .. n] é crescente se S[1] ≤ S[2] ≤ ⋯ ≤ S[k]. Adotaremos a abreviatura SSC para dizer subsequência crescente. Uma SSC de A[1 .. n] é máxima se não existe uma SSC mais longa.

Problema da SSC máxima:  Encontrar uma SSC máxima de uma sequência A[1 .. n].

Para simplificar, vamos tratar apenas de encontrar o comprimento de uma SSC máxima. Mas qualquer algoritmo que encontre o comprimento poderá ser adaptado para encontrar a correspondente SSC. Além disso, vamos supor que a sequência A[1 .. n] não é vazia, ou seja, que n ≥ 1. Com isso, toda instância do problema tem uma solução de comprimento não nulo.

Redução a um problema auxiliar

O caminho para a solução do problema da SSC máxima passa por um problema auxiliar. Para enunciar esse problema, precisamos da seguinte definição: uma subsequência direita de A[1 .. n] é qualquer subsequência D[1 .. k] de A[1 .. n] tal que o índice k de D casa com o índice n de A. É fácil constatar que uma subsequência D[1 .. k] de A[1 .. n] é direita se e somente se D[k] = A[n].

Estamos interessados em subsequências direitas que são crescentes. Adotaremos a abreviatura SSDC para a expressão subsequência direita crescente. Agora podemos enunciar o problema auxiliar:

Problema da SSDC máxima:  Encontrar uma SSDC máxima de uma sequência A[1 .. n].

A relação entre o problema auxiliar e o problema original é simples: uma SSC máxima de A[1 .. n] é a mais longa das SSDCs máximas de A[1 .. m] para m = 1, 2, … , n.  Se c[m] é o comprimento de uma SSDC máxima de A[1 .. m] então o seguinte algoritmo devolve o comprimento de uma SSC de A[1 .. m]:

Resta apenas calcular c[m] para m = 1, 2, … , n. Para isso, é preciso resolver o problema auxiliar. É o que faremos a seguir.

Algoritmo de programação dinâmica

Para resolver o problema da SSDC máxima, vamos recorrer à técnica da programação dinâmica. A instância A[1 .. n] do problema é resolvida a partir das subinstâncias A[1 .. m]. Os comprimentos das soluções das subinstâncias são guardados numa tabela c[1 .. n] e cada c[m] é calculado a partir de c[1 .. m−1].

No fim de cada execução do bloco de linhas 2-5,  c[m]  é o comprimento de uma SSDC máxima de A[1 .. m] , como mostraremos a seguir.

O algoritmo está correto.  Cada execução do bloco de linhas 2-5 do algoritmo calcula c[m] a partir de c[1 .. m−1] usando a recorrência

onde o máximo é tomado sobre todos os índices i em 1 .. m−1 para os quais A[i] ≤ A[m]. O valor inicial da recorrência é c[m] = 1, e esse valor se aplica aos casos em que não existe i em 1 .. m−1 tal que A[i] ≤ A[m].  Para mostrar que a recorrência (A) tem o efeito desejado, é preciso provar que o problema da SSDC máxima é dotado da seguinte estrutura recursiva:

se D[1 .. k] é uma SSDC máxima de A[1 .. m] e k ≥ 2 então existe i em 1 .. m−1 tal que D[1 .. k−1] é uma SSDC máxima de A[1 .. i]. 

Desempenho.  É fácil ver que o consumo de tempo do algoritmo SSDC-Max-Prog-Din é proporcional ao número de execuções da comparação A[i] ≤ A[m] na linha 4. Esse número é  ∑_{1 ≤ m ≤ n} (m − 1) = n(n−1)/2. Portanto, o algoritmo consome

Θ(n²)

unidades de tempo, tanto no pior quanto no melhor caso.  (Outra maneira de ver isso: a tabela c tem n posições e o cálculo do valor final de cada posição consome no máximo n unidades de tempo.)

De volta ao problema original

Agora que resolvemos o problema auxiliar podemos voltar ao problema da SSC máxima. Para obter o comprimento de uma SSC máxima de A[1 .. n], basta encontrar o máximo da tabela c[1 .. n]:

A linha 1 consome Θ(n²) unidades de tempo e as demais linhas consomem Θ(n) unidades de tempo. Portanto, o algoritmo é quadrático.

Apêndice: identidade minimax

O problema da SSC máxima goza de uma propriedade minimax interessante. (Trata-se de uma manifestação da dualidade em programação linear.)  Digamos que uma cobertura de A[1 .. n] é um conjunto de subsequências de A[1 .. n] dotada da seguinte propriedade: todo elemento de A[1 .. n] pertence a pelo menos uma das subsequências do conjunto. Se todas as sequências da cobertura forem estritamente decrescentes, temos uma CSSED (cobertura por subsequências estritamente decrescentes). Uma CSSED de A[1 .. n] é mínima se não existe outra CSSED com menos subsequências.

É fácil verificar que toda CSSED de A[1 .. n] é pelo menos tão grande quanto qualquer SSC. Portanto, se uma CSSED tem o mesmo tamanho que uma SSC então a CSSED é mínima e a SSC é máxima. Não é muito difícil verificar a seguinte propriedade minimax: para qualquer A[1 .. n],

o comprimento de uma SSC máxima é igual ao tamanho de uma CSSED mínima.

É um ótimo exercício modificar o algoritmo da SSC máxima para que ele devolva também uma CSSED mínima.