A Programação Dinâmica (PD) é uma técnica poderosa para resolver problemas complexos, dividindo-os em subproblemas menores e armazenando os resultados para evitar recálculos. Este artigo explora a aplicação da PD em três problemas clássicos envolvendo sequências e subarrays: a Subsequência Crescente Mais Longa, a Subsequência Contínua Crescente Mais Longa e o Subarray Repetido Mais Longo.

1. Subsequência Crescente Mais Longa (LIS)

Dada uma sequência de números inteiros, o objetivo é encontrar o comprimento da subsequência crescente mais longa.

Abordagem de Programação Dinâmica

• Estado da DP: Definimos comprimentosLIS[k] como o comprimento da subsequência crescente mais longa que termina no elemento sequencia[k].
• Fórmula de Recorrência: Para cada elemento sequencia[i] (começando do segundo elemento), iteramos por todos os elementos sequencia[j] anteriores (onde j < i). Se sequencia[i] for maior que sequencia[j], isso significa que sequencia[i] pode estender a subsequência crescente que termina em sequencia[j]. Atualizamos comprimentosLIS[i] para ser o valor máximo entre o seu comprimento atual e comprimentosLIS[j] + 1.
• Inicialização: Cada elemento comprimentosLIS[k] é inicializado com 1, pois um único elemento já é uma subsequência crescente de comprimento 1.
• Ordem de Traversal: Iteramos com i de 1 até n-1 (onde n é o tamanho da sequência) e, para cada i, iteramos com j de 0 até i-1.
• Resultado Final: O resultado é o valor máximo encontrado em todo o array comprimentosLIS.

Implementação em Java

class Solution {
   public int calcularLIS(int[] sequencia) {
       if (sequencia == null || sequencia.length == 0) {
           return 0;
       }

       int[] comprimentosLIS = new int[sequencia.length];
       // Inicializa cada elemento com 1, pois um único elemento é uma LIS de comprimento 1.
       Arrays.fill(comprimentosLIS, 1);

       int comprimentoMaximoGlobal = 1; // O menor comprimento possível é 1 (se a sequência não for vazia).

       // Itera pela sequência, começando do segundo elemento.
       for (int i = 1; i < sequencia.length; i++) {
           // Para o elemento atual 'sequencia[i]', verifica todos os elementos anteriores.
           for (int j = 0; j < i; j++) {
               // Se 'sequencia[i]' for maior que 'sequencia[j]',
               // podemos estender a LIS que termina em 'sequencia[j]'.
               if (sequencia[i] > sequencia[j]) {
                   // Atualiza o comprimento LIS para 'sequencia[i]'.
                   // Comparamos o valor atual de comprimentosLIS[i] com (comprimentosLIS[j] + 1).
                   comprimentosLIS[i] = Math.max(comprimentosLIS[i], comprimentosLIS[j] + 1);
               }
           }
           // Atualiza o comprimento máximo global encontrado até o momento.
           comprimentoMaximoGlobal = Math.max(comprimentoMaximoGlobal, comprimentosLIS[i]);
       }

       return comprimentoMaximoGlobal;
   }
}

2. Subsequência Contínua Crescente Mais Longa (LCIS)

Diferentemente da LIS, esta variação busca o comprimento da subsequência crescante que também é contígua no aray original.

Abordagem de Programação Dinâmica

• Estado da DP: tamanhosContinuos[k] representa o comprimento da subsequência crescente contínua mais longa que termina no índice k.
• Fórmula de Recorrência: Se o elemento atual elementos[i] for maior que o elemento anterior elementos[i-1], então a subsequência contínua pode ser estendida. Assim, tamanhosContinuos[i] será tamanhosContinuos[i-1] + 1. Caso contrário, a continuidade é quebrada e tamanhosContinuos[i] é 1 (o próprio elemento inicia uma nova subsequência).
• Inicialização: Todos os elementos de tamanhosContinuos são inicializados com 1.
• Ordem de Traversal: Um único loop de i de 1 até n-1.
• Resultado Final: O maior valer em tamanhosContinuos.

Implementação em Java

class Solution {
   public int encontrarComprimentoLCIS(int[] elementos) {
       if (elementos == null || elementos.length == 0) {
           return 0;
       }

       int[] tamanhosContinuos = new int[elementos.length];
       // Cada elemento, por si só, é uma LCIS de comprimento 1.
       Arrays.fill(tamanhosContinuos, 1);

       int maiorComprimentoGeral = 1;

       // Itera a partir do segundo elemento do array.
       for (int i = 1; i < elementos.length; i++) {
           // Se o elemento atual for maior que o anterior, estende a sequência contínua.
           if (elementos[i] > elementos[i-1]) {
               tamanhosContinuos[i] = tamanhosContinuos[i-1] + 1;
           }
           // Se não for maior, tamanhosContinuos[i] permanece 1,
           // indicando o início de uma nova subsequência contínua.
           
           // Atualiza o maior comprimento encontrado em todo o array.
           maiorComprimentoGeral = Math.max(maiorComprimentoGeral, tamanhosContinuos[i]);
       }
       return maiorComprimentoGeral;
   }
}

3. Subarray Repetido Mais Longo

Este problema consiste em encontrar o comprimento do maior subarray que ocorre em dois arrays dados.

Abordagem de Programação Dinâmica

• Estado da DP: Usamos uma matriz 2D, tabelaDp[r][c], para armazenar o comprimento do maior subarray comum que termina em arrPrimeiro[r-1] e arrSegundo[c-1]. A indexação r-1 e c-1 é utilizada para facilitar o tratamento dos casos base (linhas/colunas zero).
• Fórmula de Recorrência: Se os elementos arrPrimeiro[r-1] e arrSegundo[c-1] forem iguais, então um subarray comum pode ser estendido a partir do par anterior. Logo, tabelaDp[r][c] será tabelaDp[r-1][c-1] + 1. Se os elementos não forem iguais, então a continuidade do subarray comum é quebrada, e tabelaDp[r][c] é 0.
• Inicialização: A matriz tabelaDp é naturalmente inicializada com zeros em Java, o que é ideal para os casos base (comprimento 0 para subarrays em índices fora dos limites ou quando a correspondência é quebrada).
• Ordem de Traversal: Loops aninhados para r de 1 até o comprimento de arrPrimeiro e para c de 1 até o comprimento de arrSegundo.
• Resultado Final: O maior valor encontrado em qualquer célula da matriz tabelaDp.

Implementação em Java

class Solution {
   public int encontrarMaiorSubarrayComum(int[] arrPrimeiro, int[] arrSegundo) {
       int n1 = arrPrimeiro.length;
       int n2 = arrSegundo.length;

       // tabelaDp[i][j] armazena o comprimento do maior subarray comum
       // que termina em arrPrimeiro[i-1] e arrSegundo[j-1].
       // Usamos tamanho n1+1 e n2+1 para simplificar o tratamento de índices 0.
       int[][] tabelaDp = new int[n1 + 1][n2 + 1];

       int maiorComprimentoTotal = 0; // Variável para rastrear o maior comprimento encontrado.

       // Preenche a tabela DP
       for (int i = 1; i <= n1; i++) {
           for (int j = 1; j <= n2; j++) {
               // Se os elementos atuais dos dois arrays forem iguais,
               // podemos estender o subarray comum do par anterior (i-1, j-1).
               if (arrPrimeiro[i-1] == arrSegundo[j-1]) {
                   tabelaDp[i][j] = tabelaDp[i-1][j-1] + 1;
                   // Atualiza o maior comprimento geral encontrado na matriz.
                   maiorComprimentoTotal = Math.max(maiorComprimentoTotal, tabelaDp[i][j]);
               }
               // Se os elementos não forem iguais, tabelaDp[i][j] permanece 0,
               // indicando que a sequência contínua foi quebrada neste ponto.
           }
       }
       return maiorComprimentoTotal;
   }
}