Subarray máximo con el algoritmo de Kadane
Kadane decide en cada posición si continuar o empezar de nuevo.
¿Qué es Subarray máximo con el algoritmo de Kadane?
Kadane decide en cada posición si continuar o empezar de nuevo.
Encuentra el segmento contiguo con mayor suma.
¿Cuándo se utiliza?
- Comprender algoritmos y estructuras de datos.
- Observar cada paso y tratar casos límite.
- Comparar tiempo de ejecución y memoria.
Código de ejemplo
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]))Resultado esperado
6Cómo funciona
Un único recorrido produce tiempo O(n) y memoria O(1).
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios prácticos
Modifica las entradas y prueba casos límite antes de usar conjuntos de datos mayores.
- Prueba una entrada vacía, un elemento y duplicados.
- Muestra el estado después de cada paso.
- Compara el rendimiento con otra solución.