Sesión 54: Algoritmo de Kadane: Máxima Submatriz 2D y Variantes Circulares (CTCI 17.24 / LeetCode 918)#

Navegación rápida:

• ← Sesión 53: Árbol de Segmentos (Segment Tree): Consultas de Rango y Actualizaciones
• Sesión 55: Aritmética de Alto Rendimiento y Números K-Múltiplos (CTCI 17.9) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_54.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión estudiamos la extensión multidimensional del célebre Algoritmo de Kadane (Joseph Kadane, 1984), aprendiendo cómo reducir problemas espaciales O(R² · C²) a tiempo cuasi-cuadrático O(R² · C) y cómo manipular arreglos circulares sin duplicar memoria. Consulta el Glosario Maestro y la Guía de Diagramas.

Algoritmo de Kadane 1D (Maximum Subarray / LeetCode 53)#

• (a) En palabras simples (intuición): Vas caminando por un sendero recogiendo monedas de oro (positivas) y esquivando deudas (negativas). Vas sumando lo que llevas en el bolsillo. Si en algún momento tus deudas acumuladas son tan pesadas que el bolsillo queda en negativo, tiras todo a la basura y vuelves a empezar de cero con la siguiente moneda. Llevar un saldo negativo solo arruinaría las ganancias futuras.
• (b) Definición técnica paso a paso: Algoritmo de programación dinámica en tiempo O(N) y espacio O(1) que encuentra el subarreglo contiguo de suma máxima. Relación de recurrencia en el paso i:

Si current_sum < 0, arrastrar ese subarreglo hacia el elemento i + 1 restaría valor; reiniciar el subarreglo en i es matemáticamente óptimo.

• (c) Cómo funciona en Rust (memoria y tipos): Se ejecuta en dos variables locales de registros de CPU (current_sum, max_so_far), sin tocar la memoria Heap.
• (d) Error típico de Junior: Inicializar max_so_far = 0; si todos los números del arreglo son negativos (ej. [-5, -2, -9]), el algoritmo reportaría falsamente 0 en lugar del elemento menos negativo (-2).

Kadane Circular (Maximum Sum Circular Subarray / LeetCode 918)#

• (a) En palabras simples (intuición): Imagina que los extremos del arreglo están unidos formando una pulsera redonda. El mejor tramo de la pulsera puede ser un pedazo normal que no toca el broche, o puede ser un pedazo que cruza el broche uniendo el final con el principio. Para encontrar el mejor tramo que da la vuelta, en lugar de calcularlo directamente, calculas el pedazo más feo y negativo del centro y se lo restas a la pulsera completa.
• (b) Definición técnica paso a paso: Dado un arreglo circular, el subarreglo de suma máxima solo puede ser de dos tipos:

1. Caso No Circular: No cruza las fronteras. Es el Kadane 1D estándar ⟹ maxₖadane.
2. Caso Circular (Envuelve los Extremos): Toma un prefijo y un sufijo. Matemáticamente equivale a:
   total_sum - minₖadane
   Donde minₖadane es el subarreglo contiguo de suma mínima encontrado mediante Kadane invertido.

• El resultado global es max(maxₖadane, ;total_sum - minₖadane).
• (c) Cómo funciona en Rust (memoria y tipos): Una sola pasada O(N) que calcula simultáneamente max_kadane, min_kadane y total_sum.
• (d) Error típico de Junior: No contemplar el caso patológico donde todos los números son negativos. En ese caso total_sum == minₖadane, lo que resultaría en total_sum - minₖadane = 0 (un subarreglo vacío no permitido). Si maxₖadane < 0, se debe retornar obligatoriamente max_kadane.

Reducción Dimensional 2D → 1D (Max Submatrix / CTCI 17.24)#

• (a) En palabras simples (intuición): Quieres encontrar el rectángulo de oro con mayor riqueza dentro de un mapa de celdas 2D. En lugar de probar todos los rectángulos posibles (O(R² C²)), eliges dos líneas horizontales imaginarias (fila superior y fila inferior) y aplastas todas las filas que quedan en medio como un acordeón, sumando cada columna vertical en un solo número. Esa matriz aplastada se convierte en una sola línea horizontal 1D donde aplicas Kadane instantáneamente.
• (b) Definición técnica paso a paso: Algoritmo para resolver la submatriz de suma máxima en tiempo O(R² · C).
• Bucle exterior para la fila superior r₁ ∈ [0, R - 1].
• Mantiene un arreglo acumulador col_sums de tamaño C, inicializado en 0.
• Bucle interior para la fila inferior r₂ ∈ [r₁, R - 1]:
• Acumula la fila r₂ en tiempo O(C): col_sums[c] += matrix[r₂][c].
• Aplica Kadane 1D sobre col_sums en O(C) para encontrar las mejores columnas c₁ y c₂.
• Actualiza el récord global [r₁, c₁, r₂, c₂].
• (c) Cómo funciona en Rust (memoria y tipos): Reutiliza un único vector contiguo col_sums: Vec<i32> de tamaño C por cada fila superior r₁, reduciendo el consumo auxiliar a O(C).
• (d) Error típico de Junior: Recalcular la suma de cada celda desde cero con sumas de prefijo 2D dentro de 4 bucles anidados, obteniendo O(R² · C²).

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Complementariedad en Kadane Circular#

Demostremos formalmente por qué la suma máxima que envuelve los extremos es total_sum - minₖadane:

Sea un arreglo de tamaño N: A = [x₀, x₁, …, x_{n-1}]. Cualquier subarreglo que cruce la frontera circular se descompone en dos segmentos contiguos disjuntos:

Los elementos que quedan fuera de este subarreglo circular forman un subarreglo contiguo no circular:

La suma total del arreglo es invariante:

Despejando la suma circular:

Para maximizar la suma del subarreglo circular, debemos minimizar la suma del subarreglo contiguo excluido:

Como el subarreglo excluido es continuo y no circular, su valor mínimo absoluto se calcula exactamente con el algoritmo de Kadane orientado a mínimos:

Análisis de Complejidad de Max Submatrix 2D (O(R² · C))#

¿Cuántas operaciones exactas realiza la compresión de acordeón?

1. Fila superior r₁: se elige de R maneras (0, 1, …, R-1).
2. Fila inferior r₂: va desde r₁ hasta R-1. La cantidad total de pares (r₁, r₂) es:
   sum_{r₁=0}^{R-1} (R - r₁) = (R(R + 1)) / (2) ≈ (R²) / (2)
3. Para cada par (r₁, r₂): - Sumar la fila r₂ al vector col_sums: C sumas. - Ejecutar Kadane 1D sobre col_sums: C comparaciones. - Costo por par: 2C operaciones.
4. Total de operaciones:
   (R²) / (2) × 2C = R² · C

Si R = 200, C = 200:

• Fuerza bruta O(R² · C²): (200)⁴ = 1,600,000,000 operaciones (≈ 16 segundos, TLE).
• Kadane 2D O(R² · C): (200)³ = 8,000,000 operaciones (≈ 0.008 segundos). ¡Una aceleración de 200×!

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Compresión de Columnas (2D a 1D)#

Consulta el diagrama vectorial:

flowchart TD
    subgraph MATRIZ_2D["Matriz Original (R filas x C columnas)"]
        direction TB
        R1["Fila r1: [ 1,  2, -1, -4 ]"]
        R_MID["... Filas intermedias acumuladas ..."]
        R2["Fila r2: [ 3,  8, 10,  1 ]"]
    end

    MATRIZ_2D -->|Compresión vertical en acordeón| COL_SUMS["Vector 1D col_sums (tamaño C):<br/>col_sums[c] = suma(matrix[r1..r2][c])"]
    COL_SUMS --> KADANE["Ejecutar Kadane 1D en O(C)<br/>Encuentra mejores columnas c1 y c2"]
    KADANE --> RECT["Submatriz Óptima:<br/>Filas [r1..r2], Columnas [c1..c2]"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Evolución de memoria durante la búsqueda de máxima submatriz:

STACK:
[ r1: usize, r2: usize, max_sum: 29, best_coords: [1, 1, 3, 3] ]
[ col_sums: Vec<i32> { ptr: 0x4400_heap, len: 4, cap: 4 } ]

HEAP (Vector col_sums reutilizado entre r2 iteraciones):
Para r1 = 1:
- r2 = 1 (fila 1): col_sums = [ -8, -3,  4,  2 ] -> Kadane max = 6 (cols 2..3)
- r2 = 2 (fila 2): col_sums += [ 3,  8, 10,  1 ]
                   col_sums = [ -5,  5, 14,  3 ] -> Kadane max = 22 (cols 1..3)
- r2 = 3 (fila 3): col_sums += [ -4, -1,  1,  7 ]
                   col_sums = [ -9,  4, 15, 10 ] -> Kadane max = 29 (cols 1..3)
                   ¡NUEVO RÉCORD MUNDIAL! max_sum = 29, coords = [1, 1, 3, 3].

MEMORIA ASIGNADA:
Solo 1 vector de C enteros = 4 * 4 = 16 bytes en Heap.
Cero asignaciones dinámicas adicionales durante el bucle de búsqueda.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: El Caso de Todos los Elementos Negativos en Kadane Circular#

• El error: Escribir ciegamente max(max_kadane, total_sum - min_kadane).
• Por qué falla: Si nums = [-3, -2, -3], total_sum = -8 y min_kadane = -8. La resta da total_sum - min_kadane = -8 - (-8) = 0. El algoritmo reportaría que la suma máxima es 0 eligiendo un subarreglo vacío, lo cual viola el requerimiento de subarreglos no vacíos.
• La solución: Si max_sum < 0, significa que todos los elementos son negativos; retornar inmediatamente max_sum:

  if max_sum < 0 { return max_sum; }

Trampa 2: Olvidar Reiniciar col_sums al Avanzar r1#

• El error: Mantener acumulado col_sums sin limpiarlo cuando la fila superior r₁ avanza.
• Por qué falla: Arrastra los valores de la fila r₁ - 1, corrompiendo la definición de que col_sums solo debe contener la suma estricta entre r₁ y r₂.
• La solución: Reinicializar en ceros col_sums al inicio de cada iteración de r₁:

  let mut col_sums = vec![0i32; cols];

Trampa 3: Asumir que la Orientación de la Matriz es Indiferente#

• El error: Ejecutar el bucle sobre filas R² · C cuando la matriz es muy alta y estrecha (ej. R = 10,000, C = 5).
• Por qué falla: (10,000)² × 5 = 5 × 10⁸ operaciones (lento).
• La solución: Si R > C, trasponer la matriz o comprimir por filas en lugar de columnas para que la complejidad sea O(min(R, C)² · max(R, C)). En este caso: 5² × 10,000 = 250,000 operaciones (2000× más rápido).

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_54.rs)#

/// Algoritmo de Kadane 1D con reconstrucción de índices.
pub fn kadane_1d(nums: &[i32]) -> (i32, usize, usize) {
    if nums.is_empty() {
        return (0, 0, 0);
    }

    let mut max_so_far = nums[0];
    let mut current_sum = nums[0];
    let mut best_start = 0usize;
    let mut best_end = 0usize;
    let mut temp_start = 0usize;

    for i in 1..nums.len() {
        if nums[i] > current_sum + nums[i] {
            current_sum = nums[i];
            temp_start = i;
        } else {
            current_sum += nums[i];
        }

        if current_sum > max_so_far {
            max_so_far = current_sum;
            best_start = temp_start;
            best_end = i;
        }
    }

    (max_so_far, best_start, best_end)
}

/// LeetCode 918: Maximum Sum Circular Subarray.
pub fn max_subarray_sum_circular(nums: &[i32]) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut total_sum = 0i32;
    let mut current_max = 0i32;
    let mut max_sum = nums[0];
    let mut current_min = 0i32;
    let mut min_sum = nums[0];

    for &x in nums {
        total_sum += x;
        current_max = x.max(current_max + x);
        max_sum = max_sum.max(current_max);

        current_min = x.min(current_min + x);
        min_sum = min_sum.min(current_min);
    }

    if max_sum < 0 {
        return max_sum;
    }

    max_sum.max(total_sum - min_sum)
}

/// CTCI 17.24: Max Submatrix 2D en O(R^2 * C).
pub fn max_submatrix_2d(matrix: &[Vec<i32>]) -> (i32, [usize; 4]) {
    if matrix.is_empty() || matrix[0].is_empty() {
        return (0, [0, 0, 0, 0]);
    }

    let rows = matrix.len();
    let cols = matrix[0].len();
    let mut max_sum = matrix[0][0];
    let mut best_coords = [0usize, 0, 0, 0];

    for r1 in 0..rows {
        let mut col_sums = vec![0i32; cols];
        for r2 in r1..rows {
            for c in 0..cols {
                col_sums[c] += matrix[r2][c];
            }

            let mut current_sum = col_sums[0];
            let mut cur_max = col_sums[0];
            let mut cur_c1 = 0usize;
            let mut cur_c2 = 0usize;
            let mut temp_c1 = 0usize;

            for c in 1..cols {
                if col_sums[c] > current_sum + col_sums[c] {
                    current_sum = col_sums[c];
                    temp_c1 = c;
                } else {
                    current_sum += col_sums[c];
                }

                if current_sum > cur_max {
                    cur_max = current_sum;
                    cur_c1 = temp_c1;
                    cur_c2 = c;
                }
            }

            if cur_max > max_sum {
                max_sum = cur_max;
                best_coords = [r1, cur_c1, r2, cur_c2];
            }
        }
    }

    (max_sum, best_coords)
}

Implementación de Referencia en Python (practica/dia_54_kadane_1d_circular_max_submatrix.py)#

from typing import List, Tuple


def max_subarray_sum_circular(nums: List[int]) -> int:
    """LeetCode 918: Kadane Circular en O(N)."""
    total_sum = 0
    current_max, max_sum = 0, nums[0]
    current_min, min_sum = 0, nums[0]

    for x in nums:
        total_sum += x
        current_max = max(x, current_max + x)
        max_sum = max(max_sum, current_max)
        current_min = min(x, current_min + x)
        min_sum = min(min_sum, current_min)

    if max_sum < 0:
        return max_sum
    return max(max_sum, total_sum - min_sum)


def max_submatrix_sum(matrix: List[List[int]]) -> int:
    """CTCI 17.24: Max Submatrix en O(R^2 * C)."""
    rows, cols = len(matrix), len(matrix[0])
    max_sum = matrix[0][0]

    for r1 in range(rows):
        col_sums = [0] * cols
        for r2 in range(r1, rows):
            for c in range(cols):
                col_sums[c] += matrix[r2][c]

            cur, cur_max = col_sums[0], col_sums[0]
            for c in range(1, cols):
                cur = max(col_sums[c], cur + col_sums[c])
                cur_max = max(cur_max, cur)

            max_sum = max(max_sum, cur_max)

    return max_sum

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Arreglo de un Solo Elemento Negativo: - Para nums = [-7], comprueba que kadane_1d(&nums) retorne (-7, 0, 0) y que max_subarray_sum_circular(&nums) retorne -7.
2. Paso Límite 2: Matriz 2D con un Solo Elemento: - Para matrix = vec![vec![-3]], verifica que max_submatrix_2d(&matrix) reporte suma -3 con coordenadas [0, 0, 0, 0].
3. Paso Límite 3: Subarreglo de Producto Máximo (LeetCode 152): - Investiga cómo se adapta la intuición de Kadane cuando la operación es multiplicación en lugar de suma, manteniendo tanto el producto máximo como el producto mínimo acumulado para contemplar que dos números negativos multiplicados producen un positivo.

Navegación final:

• ← Sesión 53: Árbol de Segmentos (Segment Tree): Consultas de Rango y Actualizaciones
• Sesión 55: Aritmética de Alto Rendimiento y Números K-Múltiplos (CTCI 17.9) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura