El subarreglo de suma máxima con el algoritmo de Kadane
En esta lección vas a usar el algoritmo de Kadane para encontrar el tramo continuo de suma máxima en una sola pasada.
Introducción
El problema
¿Cuál fue la mejor racha de días de una acción, el tramo de la temporada con más puntos, el tramo más rentable de un viaje? Todas son preguntas de subarreglo máximo. Revisar cada inicio y cada final posible es lento. El algoritmo de Kadane lo resuelve en una sola pasada.
Imagínalo así
El algoritmo de Kadane es como recorrer un camino recogiendo oro y pagando peajes. Llevas un monedero para el tramo actual. Cuando el monedero queda en negativo, cargarlo solo te perjudica, así que lo tiras y empiezas de cero. También recuerdas el monedero más lleno que has tenido.
current = max(value, current + value)👛 Quédate el monedero, o empieza de cero si es peorbest = max(best, current)🏆 Recuerda el monedero más lleno hasta ahoracurrent = best = values[0]🚩 Empieza con el primer tramo6💰 Mejor tramo: 4, -1, 2, 1El problema del subarreglo máximo pide la mayor suma de elementos consecutivos de una lista. El algoritmo de Kadane lo resuelve en tiempo O(n) llevando la cuenta de la mejor suma que termina en cada posición.
Puntos clave
currentes la mejor suma de una racha que termina en el valor actual.current = max(value, current + value)empieza una racha nueva cuando la anterior solo bajaría la suma.best = max(best, current)guarda la mejor suma vista hasta ahora en cualquier punto.- Empezar ambos desde
values[0]hace que funcionen las listas con solo números negativos.
¿Cuándo se usa?
- Mejor periodo en series temporales: beneficios, puntuaciones, temperaturas.
- Aprender una idea clásica de programación dinámica en una sola pasada.
- Preguntas de entrevista sobre arrays (arreglos).
Cuándo no hace falta
- Necesitas el inicio y el final de la mejor racha: guarda los índices además de las sumas.
- El orden de los valores no tiene sentido: entonces las rachas de elementos consecutivos no significan nada.
Código de ejemplo
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 de la ejecución
6
Explicación del código
Para cada elemento, la variable current elige entre dos opciones: empezar un tramo nuevo a partir de ese elemento o alargar el tramo anterior con current + value. La variable best guarda la mayor suma encontrada. Con los datos de ejemplo, el tramo [4, -1, 2, 1] da la suma máxima, 6. El algoritmo se ejecuta en O(n) y solo usa O(1) de memoria.
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Errores comunes
Empezar desde 0
Si todos los valores son negativos, la respuesta sería 0, y eso es incorrecto.
current = best = 0
current = best = values[0]
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de 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. Intermedio