Subarray máximo com algoritmo de Kadane
Kadane decide em cada posição se continua ou recomeça.
O que é Subarray máximo com algoritmo de Kadane?
Kadane decide em cada posição se continua ou recomeça.
Encontre o segmento contíguo de maior soma.
Quando usar?
- Entender algoritmos e estruturas de dados.
- Observar cada etapa e tratar casos de borda.
- Comparar tempo de execução e memória.
Código de exemplo
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]))Saída esperada
6Como funciona
Uma passagem resulta em tempo O(n) e memória O(1).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Altere as entradas e teste casos de borda antes de usar conjuntos de dados maiores.
- Teste entrada vazia, um elemento e duplicados.
- Mostre o estado após cada etapa.
- Compare o desempenho com outra solução.