24 de Março
Subarray máximo
Como perceber que a pergunta certa e se a soma anterior ainda ajuda ou se já esta atrapalhando.
Arrays e Programação Dinamica Iniciante 18 min TypeScript
Dado um array de inteiros nums, encontre o subarray contiguo com a maior soma e retorne essa soma.
Exemplo:
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
O subarray [4, -1, 2, 1] tem soma 6.
O que perceber antes de codar
- O subarray precisa ser contiguo. Não vale pular elementos.
- A resposta pode ser um único elemento.
- Se todos os numeros forem negativos, o melhor resultado ainda existe.
Erros comuns
- somar só os positivos e esquecer que precisa ser contiguo
- reiniciar em `0` e quebrar o caso em que todos os numeros sao negativos
Passo 1 — Entender a palavra que muda tudo
O problema fala em subarray contiguo.
Isso mata uma leitura errada bem comum: escolher numeros espalhados que parecem bons e somar tudo.
Aqui não pode pular.
O trecho precisa ser um bloco seguido.
Passo 2 — Escrever a versão inicial correta
Uma versão inicial boa e testar todos os subarrays possiveis, mas somando de forma incremental:
export function maxSubArray(nums: number[]): number {
let best = -Infinity
for (let start = 0; start < nums.length; start += 1) {
let sum = 0
for (let end = start; end < nums.length; end += 1) {
sum += nums[end]
best = Math.max(best, sum)
}
}
return best
}
Funciona. Mas ainda testa todos os começos contra todos os finais.
Passo 3 — Perguntar o que importa na posição atual
Quando você chega em nums[i], o que quer saber?
Não precisa da melhor soma do array inteiro ainda.
A pergunta local e:
qual e a melhor soma de um subarray que termina exatamente aqui?
E ai entra o ponto central:
- se a soma anterior ajuda, continue
- se a soma anterior atrapalha, recomece no valor atual
Passo 4 — Guardar a melhor soma que termina aqui
Isso vira uma recorrencia simples:
bestEndingHere = max(value, bestEndingHere + value)
Depois, compare isso com a melhor resposta global.
Essa e a ideia inteira de Kadane.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function maxSubArray(nums: number[]): number {
// sua solução aqui
return 0
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(1)
Solução 1 — Testar todos os subarrays O(n²)
Uma versão inicial decente e fixar o início e ir estendendo o fim.
export function maxSubArray(nums: number[]): number {
let best = -Infinity
for (let start = 0; start < nums.length; start += 1) {
let sum = 0
for (let end = start; end < nums.length; end += 1) {
sum += nums[end]
best = Math.max(best, sum)
}
}
return best
}Correta, mas ainda quadratica.
Solução 2 — Kadane O(n)
Se a pergunta local e “qual a melhor soma que termina aqui?”, uma passada basta.
export function maxSubArray(nums: number[]): number {
let bestEndingHere = nums[0]
let bestOverall = nums[0]
for (let index = 1; index < nums.length; index += 1) {
const value = nums[index]
bestEndingHere = Math.max(value, bestEndingHere + value)
bestOverall = Math.max(bestOverall, bestEndingHere)
}
return bestOverall
}O algoritmo parece curto porque a pergunta foi reduzida para a decisão certa.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial testa todos os subarrays e custa
O(n²). A versão otimizada guarda a melhor soma de subarray que termina na posição atual. Se a soma anterior ajudar, eu continuo. Se atrapalhar, eu recomeco no valor atual. Isso reduz paraO(n).
Isso mostra que você:
- respeitou a restrição de contiguidade
- transformou o problema global em uma pergunta local
- explicou Kadane como raciocínio, não como nome decorado
Quando esse padrão aparece de novo
Muita gente descreve Kadane como uma forma de programacao dinamica com estado pequeno.
Em alguns casos, ele também parece guloso, porque a decisão local de continuar ou recomecar e exatamente o que mantem o melhor trecho vivo.
Esse padrão reaparece quando você precisa:
- decidir entre continuar ou recomecar
- manter uma melhor resposta local durante a passada
- transformar
programacao dinamicaem estado pequeno - explicar por que uma escolha local funciona
O ponto não e decorar “Kadane”.
O ponto e perceber quando o estado certo e “melhor resposta terminando aqui”.