Esta página resolve o problema da subsequência crescente máxima. Esse problema é uma boa introdução à técnica de programação dinâmica.
Veja o capítulo 15 (em especial o problema 15.4-5) de CLRS. Veja também o verbete Longest increasing subsequence problem na Wikipedia. Veja ainda a página Sequence Comparison: Some Theory and Some Practice de Imre Simon.
Suponha que A[1..n] é uma sequência de números naturais. Uma subsequência de A[1..n] é o que sobra depois que um conjunto arbitrário de termos é apagado. (Não confunda subsequência com segmento: um segmento de A[1..n] é o que sobra depois que apagamos um número arbitrário de termos no início de A e um número arbitrário de termos no fim de A.)
Em outras palavras, B[1..k] é uma subsequência de A[1..n] se existem índices i1,i2,…,ik tais que 1 ≤ i1 < i2 < … < ik ≤ n e
B[1] = A[i1], B[2] = A[i2], … , B[k] = A[ik] .
Dizemos que o índice 1 de B casa com o índice i1 de A, que o índice 2 de B casa com o índice i2 de A, etc. Cuidado: podemos ter B[5] = A[19], por exemplo, sem que o índice 5 de B esteja casado com índice 19 de A.
Adotaremos a abreviatura ssc para dizer "subsequência crescente". Uma ssc de A[1..n] é máxima se não existe outra ssc mais longa.
Problema da ssc máxima: Encontrar o comprimento de uma ssc máxima de A[1..n].
Exemplos:
| Guloso (A, n, m) |
| 1 _ k ← 1 |
| 2 _ B[k] ← A[m] |
| 3 _ para i ← m+1 até n faça |
| 4 ____ se B[k] ≤ A[i] |
| 5 ______ então k ← k+1 |
| 6 ______ então B[k] ← A[i] |
| 7 _ devolva k |
Para que possamos formular um algoritmo recursivo para um problema, é preciso que o problema tenha "estrutura recursiva", ou seja, é preciso que toda solução de uma instância do problema "contenha" soluções de instâncias menores (ou melhor, de subinstâncias da instância dada).
O problema da ssc máxima não parece ter estrutura recursiva (veja exercício acima), mas um parente próximo do problema tem. Para introduzir esse parente, precisamos da seguinte definição: uma ssc com término fixo de A[1..n] é qualquer ssc B[1..k] de A[1..n] tal que o índice k de B casa com o índice n de A. Adote a abreviatura ssctf para a expressão "ssc com término fixo". Eis o novo problema:
Problema da ssctf máxima: Encontrar o comprimento de uma ssctf de A[1..n] que tenha comprimento máximo.
O problema da ssctf máxima tem estrutura recursiva. De fato, se B[1..k] é uma ssctf máxima de A[1..n] então existe i tal que B[1..k−1] é ssctf máxima de A[1..i] . O seguinte algoritmo usa essa estrutura recursiva para resolver o problema:
| SSCTF-Max-Rec (A, n) |
| 1 _ c ← 1 |
| 2 _ para i ← n−1 decrescendo até 1 faça |
| 3 ____ se A[i] ≤ A[n] |
| 4 _______ então d ← SSCTF-Max-Rec (A, i) |
| 5 _______ então se d+1 > c então c ← d+1 |
| 6 _ devolva c |
(O algoritmo supõe que n ≥ 1. O caso n = 1 é a base da recursão.) O algoritmo é muito ineficiente, pois invoca SSCTF-Max-Rec (A, i) muitas vezes com o mesmo valor de i.
Para resolver o problema da ssc máxima, basta invocar SSCTF-Max-Rec (A, m) com m = 1,2,…,n e escolher o maior resultado.
Para melhorar dramaticamente a eficiência da solução recursiva acima, basta recorrer à técnica da programação dinâmica. Como no algoritmo recursivo, cada instância do problema é resolvida a partir da solução de suas subinstâncias. As soluções das subinstâncias são guardadas numa tabela, digamos c[1..n]. Para cada m,
c[m] é o comprimento de uma ssctf máxima de A[1..m].
A estrutura recursiva do problema garante que c[m] = max{1+c[i] : i < m e A[i] ≤ A[m]}. É fácil traduzir essa recorrência em código e assim preencher a tabela c da esquerda para a direita:
| SSCTF-Max-PD (A, n) |
| 1 _ para m ← 1 até n faça |
| 2 ____ c[m] ← 1 |
| 3 ____ para i ← m−1 decrescendo até 1 faça |
| 4 _______ se A[i] ≤ A[m] e c[i]+1 > c[m] |
| 5 __________ então c[m] ← c[i]+1 |
| 6 _ devolva c[1..n] |
Quanto tempo o algoritmo consome no pior caso? É fácil ver que o consumo de tempo é proporcional ao número de execuções da comparação "A[i] ≤ A[m]" na linha 4. Esse número é 0+1+...+(n−1) = n(n−1)/2. (Outra maneira de ver isso: a tabela c tem n posições e o cálculo de cada uma delas consome no máximo n unidades de tempo.) Portanto, o algoritmo consome
unidades de tempo no pior caso.
De volta ao problema original: para obter o comprimento de uma ssc máxima de A[1..n], basta calcular o máximo do vetor c[1..n], o que pode ser feito em Ο(n) unidades de tempo.
| SSC-Max (A, n) |
| 1 _ t[0] ← 0 |
| 2 _ para m ← 1 até n faça |
| 3 ____ i ← m |
| 4 ____ repita i ← i−1 |
| 5 ______ até que i = 0 ou A[i] ≤ A[m] |
| 6 ____ t[m] ← max (t[m−1], t[i]+1) |
| 7 _ devolva t[n] |
(No fim de cada execução da linha 6, t[m] é o comprimento de uma ssc máxima de A[1..m].)
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).
É fácil verificar que, para qualquer sequência A[1..n], toda cssed é 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.)
Por exemplo, o conjunto de sequências {(9,6,4), (5,3), (7), (9,6,4)} é 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.
Uma cssed de A[1..n] é mínima se não existe outra cssed com menos subsequências. 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.