[Enunciado] Queremos provar que o problema da SSDC máxima tem estrutura recursiva. Mais precisamente, queremos provar que se D[1 .. k] é uma SSDC máxima de A[1 .. m] e k ≥ 2 então
D[1 .. k−1] é SSDC máxima de A[1 .. i] para algum i em 1 .. m−1.
PROVA: É claro que o índice k − 1 de D casa com algum índice i de A que pertence ao intervalo 1 .. m−1. Portanto, D[1 .. k−1] é uma SSDC de A[1 .. i]. Resta mostrar que D[1 .. k−1] é uma SSDC máxima de A[1 .. i]. Suponha então, para obter uma contradição, que A[1 .. i] tem uma SSDC de comprimento maior que k−1, digamos X[1 .. k]. Então
X[k] = A[i] = D[k−1] ≤ D[k] = A[m].
Logo, podemos acrescentar A[m] ao final de X[1 .. k] para obter uma SSC mais longa. Digamos que a nova SSC é X[1 .. k+1]. Então X[1 .. k+1] é uma SSDC de A[1 .. m] e tem comprimento maior que o comprimento de D[1 .. k]. Como D[1 .. k] era máxima por hipótese, temos uma contradição. Essa contradição mostra que D[1 .. k−1] é, de fato, uma SSDC máxima de A[1 .. i].
Exemplo A.
A figura ilustra a prova.
Cada A
indica um elemento da sequência A[1 .. m],
cada D
indica um elemento da sequência D[1 .. k] e
cada X
indica um elemento da sequência X[1 .. k].
É claro que letras na mesma vertical representam o mesmo número.
| A | A | A | A | A | A | A | A | A | A | A | A | A | ||
| D | D | D | D | D | ||||||||||
| X | X | X | X | X | ? |