Algoritmos en Python

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.

  • Intermedio
  • 2 min de lectura
  • 1 ejemplo ejecutable

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.

De una carretera de peaje al código
current = max(value, current + value)👛 Quédate el monedero, o empieza de cero si es peor
best = max(best, current)🏆 Recuerda el monedero más lleno hasta ahora
current = best = values[0]🚩 Empieza con el primer tramo
6💰 Mejor tramo: 4, -1, 2, 1
Alarga la racha mientras sume; vuelve a empezar cuando no.
En una frase

El 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

  1. current es la mejor suma de una racha que termina en el valor actual.
  2. current = max(value, current + value) empieza una racha nueva cuando la anterior solo bajaría la suma.
  3. best = max(best, current) guarda la mejor suma vista hasta ahora en cualquier punto.
  4. 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

Ejecutar 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]))
Obtén un botón Run para este ejemplo

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.

  1. Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
  2. Muestra el estado después de cada paso para ver el algoritmo en acción.
  3. Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Ejecutar en el compilador de Python →

Errores comunes

Empezar desde 0

Si todos los valores son negativos, la respuesta sería 0, y eso es incorrecto.

Problema
current = best = 0
Solución
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.

Todos los retos