Álgoritmo de Kadane – Suma máxima de subarray de forma eficiente
El problema: imagina un juego en el que cada ronda sumas o restas puntos. Quieres elegir una secuencia de rondas consecutivas que dé la mayor puntuación posible. Esto se conoce como el problema de la submatriz o subarray máximo.
Solución ingenua: podrías comprobar todas las submatrices consecutivas y sumar cada una. Por ejemplo el arreglo [2, -3, 6] tiene las siguientes submatrices consecutivas y sus sumas: [2] = 2, [2, -3] = -1, [2, -3, 6] = 5, [-3] = -3, [-3, 6] = 3, [6] = 6. La suma máxima es 6. Este método es correcto pero muy lento para arreglos grandes con complejidad de tiempo O(n²).
Algoritmo de Kadane (solución eficiente O(n)): Kadane resuelve el problema en tiempo lineal O(n) y ocupa O(1) de memoria adicional. Es una técnica inspirada en programación dinámica pero extremadamente simple y eficiente.
Conceptos clave: usamos dos variables. currentSum mantiene la suma acumulada de la submatriz candidata. maxSum guarda la mejor suma encontrada hasta el momento. Recorremos el arreglo una sola vez y en cada paso actualizamos ambas variables.
Lógica del algoritmo: para cada elemento x del arreglo hacemos currentSum += x para intentar extender la submatriz actual. Si currentSum > maxSum actualizamos maxSum. Si currentSum < 0 reiniciamos currentSum a 0 porque una suma negativa perjudica cualquier submatriz futura que la incluya.
Implementación en JavaScript: function maxSubArray(arr) { let currentSum = 0; let maxSum = -Infinity; for (let x of arr) { currentSum += x; if (currentSum > maxSum) { maxSum = currentSum; } if (currentSum < 0) { currentSum = 0; } } return maxSum; }
Ejemplo paso a paso con arr = [2, -1, 3, -4, 5, -2, 2]: al iniciar currentSum = 0 y maxSum = -Infinity, tras procesar 2 currentSum = 2 maxSum = 2, tras -1 currentSum = 1 maxSum = 2, tras 3 currentSum = 4 maxSum = 4, tras -4 currentSum = 0 (se resetea) maxSum = 4, tras 5 currentSum = 5 maxSum = 5, tras -2 currentSum = 3 maxSum = 5, tras 2 currentSum = 5 maxSum = 5. Resultado final maxSum = 5.
Caso especial de todos negativos: Kadane funciona también si todos los valores son negativos porque inicializamos maxSum con -Infinity, por lo que devolverá el mayor valor negativo en lugar de cero.
Resumen: Kadane resuelve el problema del subarray máximo en tiempo O(n) y espacio O(1) usando solo currentSum y maxSum. Reiniciamos currentSum cuando pasa a negativo porque cualquier prefijo negativo reduce la suma futura. Es una solución concisa, rápida y óptima para este problema clásico.
En Q2BSTUDIO aplicamos principios como los del algoritmo de Kadane para construir soluciones de software a medida robustas y eficientes. Si buscas desarrollar aplicaciones a medida o software a medida optimizado, nuestro equipo de desarrollo crea arquitecturas escalables y limpias. También integramos capacidades de inteligencia artificial y agentes IA para automatizar decisiones y mejorar procesos de negocio, además de ofrecer servicios de ciberseguridad, pentesting, servicios cloud aws y azure, servicios inteligencia de negocio y soluciones con power bi.
Palabras clave relevantes: aplicaciones a medida, software a medida, inteligencia artificial, ciberseguridad, servicios cloud aws y azure, servicios inteligencia de negocio, ia para empresas, agentes IA, power bi. Contacta con Q2BSTUDIO para llevar tu proyecto desde la idea hasta la producción con técnicas y buenas prácticas que garantizan rendimiento y seguridad.