Subarray Máximo e Subarray de Produto Máximo

O problema do subvetor de soma máxima solicita que você encontre o subvetor contíguo dentro de um vetor unidimensional de números que tenha a maior soma. Por exemplo, em [-2, 1, -3, 4, -1, 2, 1, -5, 4], o subvetor [4, -1, 2, 1] fornece a soma máxima de 6. Uma abordagem de força bruta O(n²) verifica todos os subvetores, mas o algoritmo de Kadane resolve o problema em O(n).

O algoritmo de Kadane percorre o vetor uma vez, mantendo uma current_sum acumulada. Para cada elemento, você decide: é melhor estender o subvetor existente ou começar novamente a partir deste elemento? Se current_sum se torna negativa, isso apenas prejudicaria qualquer subvetor futuro, então reinicie. A recorrência é current_sum = max(num, current_sum + num).

Vamos acompanhar o algoritmo de Kadane em [-2, 1, -3, 4, -1, 2, 1, -5, 4]: começamos com a soma atual igual a -2 e o máximo igual a -2. Em 1: soma atual=max(1,-2+1)=1, máximo=1. Em -3: soma atual=max(-3,1-3)=-2, máximo=1. Em 4: soma atual=max(4,-2+4)=4, máximo=4. Em -1: soma atual=3, máximo=4. Em 2: soma atual=5, máximo=5. Em 1: soma atual=6, máximo=6. Em -5: soma atual=1. Em 4: soma atual=5, máximo=6. O algoritmo identifica corretamente o subvetor que termina no índice 6 como o ideal.

Se o entrevistador solicitar que você retorne o próprio subvetor (não apenas a soma), será necessário acompanhar os índices inicial e final. Ao reiniciar (porque num > current_sum + num), atualize um temp_start. Ao atualizar max_sum, salve temp_start como start e o índice atual como end. Isso acrescenta uma sobrecarga O(1) ao mesmo algoritmo O(n).

O problema do subvetor de produto máximo é mais complexo que a variante da soma por causa dos números negativos. Dois números negativos, quando multiplicados, resultam em um número positivo; assim, um produto muito negativo pode se tornar o máximo depois de ser multiplicado por outro número negativo. Para [2, 3, -2, 4], a resposta é 6 ([2, 3]). Para [-2, 0, -1], a resposta é 0. Precisamos acompanhar os produtos máximo e mínimo a cada etapa.

A principal ideia é: em cada posição, o produto máximo atual é um de num, max_so_far * num ou min_so_far * num (este último ajuda quando um número negativo transforma o mínimo em máximo). O mesmo vale para o mínimo. Atualize ambos cur_max e cur_min simultaneamente usando os valores anteriores para evitar usar valores já atualizados na mesma etapa.

Considere [-3, -10, 5]. Depois de processar -3: máximo=-3, mínimo=-3. Depois de -10: os candidatos são (-10, 30, 30) → máximo=30, mínimo=-10. Depois de 5: os candidatos são (5, 150, -50) → máximo=150. Sem acompanhar min_prod, você perderia a inversão que ocorre quando um mínimo muito negativo é multiplicado por outro número negativo. Calcule sempre max e min a partir dos mesmos valores anteriores para evitar um erro de leitura de valor desatualizado.

Um zero no vetor reinicia ambos os produtos acumulados para zero, dividindo efetivamente o vetor em subvetores independentes. Quando num = 0, tanto max_prod * 0 = 0 quanto min_prod * 0 = 0, portanto os três candidatos se tornam 0, e o resultado máximo anterior é preservado. Não é necessário nenhum código para casos especiais — a fórmula geral trata os zeros naturalmente.

Uma abordagem alternativa percorre o vetor da esquerda para a direita e da direita para a esquerda, redefinindo o produto acumulado para 1 ao encontrar zero. O subvetor de produto máximo nunca atravessa um zero; portanto, se um número negativo piorar o resultado em uma direção, a varredura inversa capturará a inversão. Essa abordagem é elegante, mas o método de acompanhamento de mínimo/máximo é mais comumente esperado em entrevistas.

Os subvetores de soma e de produto diferem de maneiras importantes. Para a soma, números negativos são sempre prejudiciais, então você reinicia de forma gananciosa. Para o produto, dois números negativos ajudam, portanto é necessário acompanhar os dois extremos. Além disso, os zeros encerram os produtos, mas são apenas levemente prejudiciais para as somas. Ao explicar a solução em entrevistas, reconheça explicitamente essas diferenças e explique por que é necessário acompanhar o mínimo antes de escrever qualquer código.

Tanto o algoritmo de Kadane (soma máxima) quanto o acompanhamento de mínimo/máximo (produto máximo) são executados em tempo O(n) e usam espaço O(1). Dicas importantes para entrevistas: (1) Para a soma máxima, mencione a alternativa de Divisão e Conquista O(n log n) para demonstrar amplitude. (2) Para o produto máximo, enfatize que você atualiza min_prod e max_prod simultaneamente a partir dos valores anteriores para evitar usar dados desatualizados. (3) Sempre esclareça: o vetor pode estar vazio? O subvetor precisa ser não vazio? (Sim, por convenção, ele precisa ser não vazio.)

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.

Nesta lição, você aprendeu: o algoritmo de Kadane resolve o subvetor de soma máxima em O(n), escolhendo estendê-lo ou reiniciá-lo em cada elemento, o subvetor de produto máximo exige acompanhar os produtos acumulados mínimo e máximo devido às inversões causadas por números negativos e os zeros reiniciam naturalmente o produto acumulado, sem código para casos especiais. Em seguida, exploraremos o problema de segmentação de palavras usando uma tabela DP unidimensional.