Algoritmo del Máximo Subarreglo (Maximum Subarray)

El problema del máximo subarreglo consiste en encontrar, dentro de un arreglo de números (positivos, negativos o cero), el subarreglo contiguo cuya suma sea la mayor posible. Es un caso clásico de programación dinámica y sirve como base para problemas más complejos en análisis de series temporales, finanzas y aprendizaje automático.

Índice de contenidos

• Definición formal
• Fuerza bruta (O(n³) y O(n²))
• Algoritmo de Kadane (O(n))
• Dividir y vencerás (O(n log n))
• Comparativa de enfoques
• Variantes y extensiones
• Casos de uso reales
• Optimización y buenas prácticas
• Troubleshooting y consideraciones de seguridad

Definición formal

Dados arr[0..n‑1], buscamos índices i y j (con 0 ≤ i ≤ j < n) que maximicen:

sum = Σ_{k=i}^{j} arr[k]

El algoritmo debe devolver tanto la suma máxima como, opcionalmente, los índices i y j.

Fuerza bruta (O(n³) y O(n²))

La solución más directa recorre todos los pares (i, j) y calcula la suma de cada subarreglo. La versión naïve tiene complejidad O(n³). Mejorando ligeramente al acumular sumas parciales, podemos lograr O(n²).

def max_subarray_bruteforce(arr):
    n = len(arr)
    max_sum = float('-inf')
    best_i = best_j = -1
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += arr[j]  # acumulación O(1)
            if current_sum > max_sum:
                max_sum = current_sum
                best_i, best_j = i, j
    return max_sum, best_i, best_j

Esta versión es útil para validar resultados de implementaciones más rápidas en pruebas unitarias.

Algoritmo de Kadane (O(n))

Kadane (1984) aprovecha la observación de que un subarreglo que termina en la posición i es óptimo si y sólo si su suma parcial es mayor que cero. La solución recorre el arreglo una sola vez, manteniendo dos variables:

• current_max: máxima suma que termina en el índice actual.
• global_max: mejor suma encontrada hasta ahora.

def kadane(arr):
    """Retorna (max_sum, start_index, end_index) usando O(n) de tiempo y O(1) de espacio.
    Funciona con números negativos, cero y positivos.
    """
    if not arr:
        raise ValueError('El arreglo no puede estar vacío')
    max_sum = current_max = arr[0]
    start = end = s = 0
    for i in range(1, len(arr)):
        # Decidir si iniciar nuevo subarreglo en i o continuar el anterior
        if arr[i] > current_max + arr[i]:
            current_max = arr[i]
            s = i
        else:
            current_max += arr[i]
        # Actualizar la mejor solución global
        if current_max > max_sum:
            max_sum = current_max
            start = s
            end = i
    return max_sum, start, end

Ejemplo de uso:

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  print(kadane(arr))  # Salida: (6, 3, 6) -> subarreglo [4, -1, 2, 1]

Dividir y vencerás (O(n log n))

Esta estrategia combina la solución recursiva de los dos mitades del arreglo con la mejor suma que cruza el punto medio. Es útil cuando se necesita procesar consultas dinámicas (p.ej., árboles de segmento).

def max_crossing(arr, left, mid, right):
    # Suma máxima que cruza el medio desde la izquierda
    left_sum = float('-inf')
    total = 0
    max_left = mid
    for i in range(mid, left - 1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total
            max_left = i
    # Suma máxima que cruza el medio desde la derecha
    right_sum = float('-inf')
    total = 0
    max_right = mid + 1
    for i in range(mid + 1, right + 1):
        total += arr[i]
        if total > right_sum:
            right_sum = total
            max_right = i
    return left_sum + right_sum, max_left, max_right
def max_subarray_divide(arr, left, right):
    if left == right:
        return arr[left], left, right
    mid = (left + right) // 2
    left_sum, l_start, l_end = max_subarray_divide(arr, left, mid)
    right_sum, r_start, r_end = max_subarray_divide(arr, mid + 1, right)
    cross_sum, c_start, c_end = max_crossing(arr, left, mid, right)
    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_sum, l_start, l_end
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_sum, r_start, r_end
    else:
        return cross_sum, c_start, c_end
# Wrapper
def max_subarray_dc(arr):
    if not arr:
        raise ValueError('Array vacío')
    return max_subarray_divide(arr, 0, len(arr) - 1)

Comparativa de enfoques

Variantes y extensiones

• Máximo subarreglo con longitud mínima: se agrega una restricción de tamaño y se usa una cola de máximos parciales.
• Máximo subarreglo circular: se combina Kadane con la suma total del arreglo para considerar subarreglos que envuelven el final.
• Máximo subarreglo en 2‑D (máxima suma de sub‑matriz): se reduce a múltiples ejecuciones de Kadane sobre columnas acumuladas.

Ejemplo de variante circular:

def max_subarray_circular(arr):
    # Caso normal con Kadane
    max_kadane, _, _ = kadane(arr)
    total = sum(arr)
    # Invertir los signos para encontrar mínima suma
    inverted = [-x for x in arr]
    min_kadane, _, _ = kadane(inverted)
    max_wrap = total + min_kadane  # Porque min_kadane es negativo
    return max(max_kadane, max_wrap) if max_wrap != 0 else max_kadane

Casos de uso reales

El algoritmo del máximo subarreglo se emplea en:

• Análisis financiero: encontrar la mejor ventana de compra‑venta de una acción (maximizar ganancia).
• Procesamiento de señales: detectar la ventana con mayor energía en una señal de audio.
• Machine Learning: optimizar funciones de pérdida que dependen de sumas parciales, como en ciertos algoritmos de clustering temporal.
• Compresión de datos: identificar bloques de alta entropía para aplicar técnicas de compresión adaptativa.

Optimización y buenas prácticas

1. Evitar conversiones costosas: mantén los datos en listas o arrays de numpy cuando trabajes con millones de elementos.
2. Vectorización: en entornos NumPy, una versión vectorizada de Kadane puede ser ~2‑3× más rápida.

   import numpy as np
   def kadane_numpy(arr):
       arr = np.asarray(arr, dtype=np.int64)
       max_ending_here = max_sofar = arr[0]
       for x in arr[1:]:
           max_ending_here = np.maximum(x, max_ending_here + x)
           max_sofar = np.maximum(max_sofar, max_ending_here)
       return int(max_sofar)
   

3. Parallelismo: la variante divide‑and‑conquer se presta a ejecución paralela usando multiprocessing o frameworks como Dask.
4. Gestión de overflow: con enteros de 64 bits en Python no hay overflow, pero al usar numpy.int32 considera convertir a int64 antes de acumular.

Troubleshooting y consideraciones de seguridad

• Entrada vacía: el algoritmo debe lanzar una excepción clara; de lo contrario, retornará -inf inesperado.
• Datos no numéricos: valida tipos antes de procesar; Python lanzará TypeError si se suman strings.
• Inyección de código en entornos web: si el arreglo proviene de una petición HTTP, sanitiza y valida el JSON para evitar payloads maliciosos.
• Consumo de memoria: no almacenes sub‑arreglos completos; mantén solo índices y sumas.

Con esta guía tienes todas las piezas necesarias para implementar, comparar y adaptar el algoritmo del máximo subarreglo a cualquier proyecto Python, desde scripts rápidos hasta sistemas de análisis en tiempo real.