Algoritmos em Python

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.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

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.

Da estrada com pedágios ao código
current = max(value, current + value)👛 Fique com a bolsa, ou comece do zero se ela for pior
best = max(best, current)🏆 Lembre a bolsa mais cheia até agora
current = best = values[0]🚩 Comece com o primeiro trecho
6💰 Melhor trecho: 4, -1, 2, 1
Estenda a sequência enquanto ela ajuda; recomece quando não ajuda.
Em uma frase

O 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

  1. current é a melhor soma de uma sequência que termina no valor atual.
  2. current = max(value, current + value) começa uma nova sequência quando a antiga só baixaria a soma.
  3. best = max(best, current) guarda a melhor soma vista em qualquer ponto até agora.
  4. 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

Executar código →
main.py
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]))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Começar do 0

Com uma entrada só de negativos, a resposta seria 0, o que está errado.

Problema
current = best = 0
Correção
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.

Todos os desafios