Subarray de soma máxima com o algoritmo de Kadane
Nesta lição, você vai usar o algoritmo de Kadane para encontrar o trecho contínuo de maior soma com uma única passada pela lista.
Introdução
O problema
Qual foi a melhor sequência de dias de uma ação, a maior série de vitórias em pontos, o trecho mais lucrativo de uma viagem? Todas são perguntas de subarray máximo. Testar cada início e fim é lento; o algoritmo de Kadane resolve em uma passada.
Pense assim
O algoritmo de Kadane é como andar por uma estrada recolhendo ouro e pagando pedágios. Você leva uma bolsa com o saldo do trecho atual. Quando a bolsa fica negativa, carregá-la só atrapalha, então você a larga e começa do zero. Você também lembra a bolsa mais cheia que já teve.
current = max(value, current + value)👛 Fique com a bolsa, ou comece do zero se ela for piorbest = max(best, current)🏆 Lembre a bolsa mais cheia até agoracurrent = best = values[0]🚩 Comece com o primeiro trecho6💰 Melhor trecho: 4, -1, 2, 1O problema do subarray máximo pede a maior soma de itens consecutivos de uma lista. O algoritmo de Kadane resolve em tempo O(n), acompanhando a melhor soma que termina em cada posição.
Pontos-chave
currenté a melhor soma de uma sequência que termina no valor atual.current = max(value, current + value)começa uma nova sequência quando a antiga só baixaria a soma.best = max(best, current)guarda a melhor soma vista em qualquer ponto até agora.- Começar os dois com
values[0]faz funcionar listas só com números negativos.
Quando usar?
- Melhor período em séries temporais: lucros, pontuações, temperaturas.
- Aprender uma ideia clássica de programação dinâmica em uma passada.
- Perguntas de entrevista sobre arrays.
Quando não é preciso
- Você precisa do início e do fim da melhor sequência: acompanhe os índices além das somas.
- Os valores não estão em uma ordem com sentido: aí sequências consecutivas não significam nada.
Código de exemplo
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Resultado da execução
6
Explicação do código
Em cada elemento, a variável current escolhe entre duas opções: começar um novo trecho a partir desse elemento ou continuar o trecho anterior com current + value. A variável best guarda a maior soma já vista. Com os dados de exemplo, o trecho [4, -1, 2, 1] dá a maior soma, que é 6. O algoritmo roda em O(n) e usa apenas O(1) de memória.
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Começar do 0
Com uma entrada só de negativos, a resposta seria 0, o que está errado.
current = best = 0
current = best = values[0]
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
- Sliding Window Maximum Report the maximum of every window of k numbers. Difícil
- Largest Adjacent-Digit Product Take every contiguous window of span digits and multiply its digits. Médio