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 (i1, i2, … , ik) de índices tal que  1 ≤ i1 < i2 < ⋯ < ikn  e

S[1] = A[i1], S[2] = A[i2], … , S[k] = A[ik] .

Dizemos que o índice 1 de S casa com o índice i1 de A, que o índice 2 de S casa com o índice i2 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 (i1, i2, … , ik) tal que  ij = 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.

Exemplo A:  Seja A a sequência (9, 5, 6, 5, 9, 6, 4, 7) e S a sequência (5, 6, 6, 7). Observe que (2, 3, 6, 8) é uma injeção de S em A e portanto S é subsequência de A. O índice 2 de S casa com o índice 3 de A e o índice 3 de S casa com índice 6 de A. Embora S[1] seja igual a A[4], o índice 1 de S não casa com o índice 4 de A.

9 5 6 5 9 6 4 7
5 6 6 7

A sequência S é uma SSC de A. A sequência (5, 6, 9) também é uma SSC de A. Esta última não é máxima pois S é mais longa. (A sequência (5, 6, 9) é apenas uma SSC maximal de A, pois não pode ser prolongada.)

9 5 6 5 9 6 4 7
5 6 9

Exercícios 1

  1. ★ Considere as sequências A = (1, 3, 2, 3) e S = (2, 1). É verdade que o índice 1 de S casa com o índice 3 de A?
  2. ★ Seja A a sequência (9, 5, 6, 5, 9, 6, 4, 7) e S a sequência (5, 6, 6, 7). Observe que S é subsequência de A. É verdade que índice 3 de S casa com o índice 4 de A? É verdade que índice 3 de S casa com o índice 3 de A?
  3. ★ Escreva um algoritmo para decidir se S[1 .. k] é uma subsequência de A[1 .. n]. Prove que seu algoritmo está correto.
  4. Encontre uma SSC máxima de (1, 2, 3, 9, 4, 5, 6).
  5. Encontre uma SSC máxima da sequência (32, 19, 32, 17, 31, 43, 30, 29, 54, 16, 28, 66, 15, 41, 65, 14, 50).
  6. Discuta o seguinte algoritmo: Para cada sequência b[1 .. n] de bits, considere a subsequência de A[1 .. n] que corresponde aos bits 1 de b. Descarte as subsequências não crescentes. Escolha a mais longa das sequências restantes.
  7. ★ O algoritmo guloso abaixo resolve o problema da SSC máxima? A rotina Último na linha 1 escolhe um índice de A entre 1 e n. Você pode imaginar que a rotina sempre devolve n, ou sempre devolve o índice de um elemento máximo de A[1 .. n], ou devolve um índice aleatório, ou outro índice qualquer.
    Guloso (A, n)
    1 . k := Último (A, n)
    2 . S[k] := A[n]
    3 . para i := n − 1 decrescendo até 1
    4 .ooo se A[i] ≤ S[k]
    5 .ooooooo S[k−1] := A[i]
    6 .ooooooo k := k − 1
    7 . devolva nk + 1
  8. ★ Acompanhe o seguinte raciocínio, que pode levar a um bom algoritmo. Suponha que S[1 .. k] é uma SSC máxima de A[1 .. n]. Há duas possibilidades: ou o índice k de S casa com o índice n de A ou não casa. No segundo caso, S[1 .. k] é uma SSC máxima de A[1 .. n−1]. (Isto é muito bom, pois reduz a instância do problema a uma instância menor.) No primeiro caso, S[1 .. k−1] é uma SSC máxima de A[1 .. n−1]?

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].

Exemplo B.  A figura mostra uma sequência A[1 .. 10], seguida de uma SSC máxima S[1 .. 6] e de uma SSDC máxima D[1 .. 5]. Note que D é mais curta que S. (Em geral, o comprimento de uma SSDC máxima é menor que ou igual ao comprimento de uma SSC máxima.)

A 40 11 90 22 33 50 60 44 70 55
S 11 22 33 50 60 70
D 11 22 33 44 55

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]:

. x := 0
. para m := 1 até n
.ooo se c[m] > x
.oooooo x := c[m]
. devolva x

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

Exercícios 2

  1. ★ Suponha que D[1 .. k] é uma subsequência de A[1 .. n]. Mostre que D[1 .. k] é uma subsequência direita de A[1 .. n] se e somente se D[k] = A[n].

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].

SSDC-Max-Prog-Din (A, n)
1 . para m := 1 até n
2 .ooo c[m] := 1
3 .ooo para i := m−1 decrescendo até 1
4 .oooooo se A[i] ≤ A[m] e c[i] + 1 > c[m]
5 .ooooooooooo c[m] := c[i] + 1
6 . devolva c[1 .. n]

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

Exemplo C.  A figura mostra uma sequência A[1 .. 10] e a correspondente tabela c[1 .. 10]. O algoritmo preenche a tabela da esquerda para a direita.

A 40 11 90 22 33 50 60 44 70 55  
c 1 1 2 2 3 4 5 4 6 5

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

  c[m] = max c[i]  +  1 , (A)

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.)

Exercícios 3

  1. Estrutura recursiva.  Prove a estrutura recursiva do problema da SSDC máxima.  [Solução.]
  2. Prove que a recorrência (A) implementa corretamente a estrutura recursiva do problema.
  3. Prove, cuidosamente, que o algoritmo SSDC-Max-Prog-Din está correto.
  4. ★ Qual a diferença entre provar que um algoritmo está correto e descrever os passos do algoritmo em português (o algoritmo faz isso, depois faz aquilo …, etc.)?
  5. Digamos que c[1 .. n] é o vetor calculado pelo algoritmo SSDC-Max-Prog-Din. É verdade que c[n] é o número de elementos do vetor A[1 .. n] que são menores ou iguais a A[n]?
  6. Tabela preenchida ao contrário.  O algoritmo SSDC-Max-Prog-Din preenche a tabela c[1 .. n] da esquerda para a direita, ou seja, de 1 para n. Escreva uma variante do algoritmo que preencha a tabela da direita para a esquerda. Ajuste a definição de SSDC de maneira apropriada. Dê a definição apropriada da tabela c[1 .. n]. Descreva a estrutura recursiva apropriada.

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]:

SSC-Max-PD (A, n)
1 . c := SSDC-Max-Prog-Din (A, n)
2 . x := 0
3 . para i := 1 até n
4 .ooo se c[i] > x
5 .oooooo x := c[i]
6 . devolva x

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

Exercícios 4

  1. Calcule uma SSC máxima da sequência (32, 19, 32, 17, 31, 43, 30, 29, 54, 16, 28, 66, 15, 41, 65, 14, 50).
  2. O algoritmo abaixo resolve o problema da SSC máxima? (O operador max na linha 6 devolve o valor do maior de seus argumentos.)
    SSC-Maxx (A, n)
    1 . c[0] := 0
    2 . para m := 1 até n
    3 .ooo i := m
    4 .ooo repita i := i−1
    5 .oooooo até que i = 0 ou A[i] ≤ A[m]
    6 .ooo c[m] := max (c[m−1], c[i]+1)
    7 . devolva c[n]
  3. ★ Sabe-se que um certo algoritmo para o problema da SSC máxima consome Ο(n lg n) unidades de tempo para processar um vetor com n elementos. Quanto tempo, no máximo, o algoritmo consumirá para processar um vetor com 1024 elementos?
  4. Escreva um algoritmo de programação dinâmica que devolva não só o comprimento de uma SSC máxima de A[1 .. n] como também a correspondente SSC.
  5. Palíndromo.  Escreva um algoritmo que receba uma sequência A[1 .. n] e devolva uma subsequência máxima de A[1 .. n] dentre as que são palíndromos. (Uma sequência S[1 .. k] é palíndromo de S[1] = S[k], S[2] = S[k−1], etc.)
  6. Número de ocorrências.  Escreva um algoritmo que conte o número de ocorrências de S[1 .. k] como subseqüência de A[1 .. n]. O seu algoritmo pode consumir tempo Ο(kn).
  7. Invente um algoritmo que resolva o problema da SSC máxima em Ο(n lg n) unidades de tempo.
  8. Subsequência comum máxima de duas sequências.  Considere o problema da subsequência comum máxima (= longest common subsequence) de duas sequências. (Por exemplo, (2, 3, 2, 1) é uma subsequência comum máxima de (1, 2, 3, 2, 4, 1, 2) e (2, 4, 3, 1, 2, 1).)  Mostre que o problema da SSC máxima é um caso especial do problema da subsequência comum máxima de duas sequências.
  9. Subsequência comum máxima de duas sequências.  Resolva o problema da subsequência comum máxima de duas sequências.

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.

Exemplo D.  As sequências (9, 6, 4), (5, 3), (7) e (9, 6, 4) constituem uma CSSED da sequência  (9, 5, 6, 3, 9, 6, 4, 7).  Esta CSSED prova que não existe uma SSC de comprimento maior que quatro. Mais que isso: como existe uma SSC de tamanho quatro — como (5, 6, 6, 7), por exemplo — a CSSED é mínima e toda SSC de tamanho quatro é máxima.

9 5 6 3 9 6 4 7

9 - 6 - - - 4 -
- 5 - 3 - - - -
- - - - - - - 7
- - - - 9 6 4 -

- 5 6 - - 6 - 7

É 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.

Exercícios 5

  1. Exiba uma SSC máxima da sequência (32, 19, 32, 17, 31, 43, 30, 29, 54, 16, 28, 66, 15, 41, 65, 14, 50). Exiba uma CSSED apropriada para provar a maximalidade da SSC.