Jardin de Conocimiento

Python · Módulo 09 · Ej 04 — Devuelve la suma de la sublista contigua con mayor suma

4 min read

Ejercicio 04 — Devuelve la suma de la sublista contigua con mayor suma

Dificultad: amarillo · Módulo 09 (Puente a NeetCode)

Enunciado

devuelve la suma de la sublista contigua con mayor suma (algoritmo de Kadane)

Cómo se resuelve

La suma máxima de una sublista contigua se resuelve con el algoritmo de Kadane: un acumulador que en cada paso decide si le conviene extender la racha actual o empezar una nueva.

  1. actual = nums[0] y maximo = nums[0] — arrancamos con el primer elemento en las dos variables. actual es la mejor suma que termina en la posición actual; maximo es la mejor suma vista en todo el recorrido.
  2. for n in nums[1:]: recorre desde el segundo elemento. actual = max(n, actual + n) es el corazón de Kadane: si arrastrar lo acumulado (actual + n) sale peor que empezar limpio en n, se descarta el pasado. Es lo mismo que “resetear” la racha cuando se ha vuelto negativa.
  3. maximo = max(maximo, actual) guarda aparte el mejor resultado, porque la mejor sublista puede terminar en cualquier posición, no necesariamente en la última.
  4. Una sola pasada y solo dos variables: O(n) tiempo y O(1) espacio, muy por debajo del O(n^2) de probar todas las sublistas.

Trampa habitual: inicializar maximo = 0. Fallaría con listas de solo negativos como [-1], donde la respuesta correcta es -1: con cero devolverías 0, una sublista vacía que el enunciado no permite. Inicializa con nums[0], no con cero.

Para practicar — cópialo y complétalo

Pega este esqueleto y completa los TODO. Es la mejor forma de aprender: inténtalo antes de mirar la solución.

# Curso de Python — Modulo 09: Puente a NeetCode
# Ejercicio 04 — PRACTICA (rellena los TODO)
# Enunciado: devuelve la suma de la sublista contigua con mayor suma (algoritmo de Kadane)
# Dificultad: amarillo
# Ejecutar: python3 ej04_practica.py
 
# PISTA: en cada paso decide si extender la sublista actual o empezar una nueva.
# actual = max(n, actual + n)   <- esta es la decision clave
# Actualiza el maximo global despues de cada decision.
 
 
def max_subarray(nums: list) -> int:
    """Devuelve la suma maxima de una sublista contigua no vacia."""
    # TODO 1: inicializa 'actual' y 'maximo' con el primer elemento de nums
    actual = ...
    maximo = ...
 
    # TODO 2: recorre nums desde el segundo elemento (nums[1:])
    for n in ...:
        # TODO 3: actualiza 'actual': max entre n solo y actual + n
        #         (decide si conviene empezar de nuevo o extender)
        actual = max(...)
 
        # TODO 4: actualiza 'maximo' si 'actual' es mayor
        maximo = max(...)
 
    # TODO 5: devuelve maximo
    return ...
 
 
# --- Pruebas (no toques esta parte) ---
if __name__ == "__main__":
    casos = [
        ([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6),
        ([1],                               1),
        ([5, 4, -1, 7, 8],                 23),
        ([-1],                             -1),
    ]
 
    for nums, esperado in casos:
        resultado = max_subarray(nums)
        estado = "OK" if resultado == esperado else "FALLO"
        print(f"[{estado}] max_subarray({nums}) = {resultado}  (esperado {esperado})")

Solución — cópiala y ejecútala

# Curso de Python — Modulo 09: Puente a NeetCode
# Ejercicio 04 — MODELO (resuelto)
# Enunciado: devuelve la suma de la sublista contigua con mayor suma (algoritmo de Kadane)
# Dificultad: amarillo
# Ejecutar: python3 ej04_modelo.py
 
# PATRON: acumulador con reset — algoritmo de Kadane.
# En cada posicion decidimos: ¿conviene extender la sublista actual
# o empezar una nueva desde aqui?
# Si actual + nums[i] < nums[i]  ->  empezamos nueva sublista en i.
# Equivale a: actual = max(nums[i], actual + nums[i])
# Coste: O(n) tiempo, O(1) espacio.
 
 
def max_subarray(nums: list) -> int:
    """Devuelve la suma maxima de una sublista contigua no vacia."""
    # Inicializamos con el primer elemento (la lista siempre tiene al menos 1)
    actual = nums[0]
    maximo = nums[0]
 
    for n in nums[1:]:               # empezamos desde el segundo elemento
        actual = max(n, actual + n)  # extender o empezar de nuevo
        maximo = max(maximo, actual) # actualizar el maximo global
 
    return maximo
 
 
# --- Pruebas manuales ---
if __name__ == "__main__":
    casos = [
        ([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6),   # sublista [4,-1,2,1]
        ([1],                               1),
        ([5, 4, -1, 7, 8],                 23),
        ([-1],                             -1),   # todos negativos -> el mayor elemento
    ]
 
    for nums, esperado in casos:
        resultado = max_subarray(nums)
        estado = "OK" if resultado == esperado else "FALLO"
        print(f"[{estado}] max_subarray({nums}) = {resultado}  (esperado {esperado})")

Cómo usarlo

Pega el código en un fichero y ejecútalo con tu toolchain habitual (o el botón de Ejecutar de tu editor). Antes de mirar la solución, intenta completar tú el esqueleto: es la mejor forma de aprender.

Conexiones

Graph View

Backlinks