El problema
Dados un arreglo de enteros nums encontrar el subarreglo con la suma mayor y devolver esa suma. Un subarreglo es una secuencia contigua no vacía de elementos dentro del arreglo sin saltos entre elementos.
Ejemplo
Entrada nums = [-2,1,-3,4,-1,2,1,-5,4] Salida 6 Explicación El subarreglo [4,-1,2,1] tiene la suma máxima 6.
Idea y pensamiento
Se puede resolver con Programación Dinámica rompiendo el problema en pasos más pequeños y reutilizando resultados. Para cada índice preguntamos cuál es la máxima suma de un subarreglo que termina exactamente en ese índice. Si conocemos la máxima suma en el índice anterior podemos elegir empezar de nuevo en el número actual nums[i] si la suma anterior es negativa o continuar el subarreglo añadiendo nums[i].
Regla de transición currentMax = Math.max(nums[i], nums[i] + currentMaxAnterior) y también llevamos la máxima global vista hasta ahora que será la respuesta.
Solución en JavaScript
const maxSubArray = (nums) => { let maxSum = nums[0]; let currentMax = 0; for (let i = 0; i < nums.length; i++) { currentMax = Math.max(nums[i], currentMax + nums[i]); let currentMaxSum = maxSum; if (currentMax > maxSum) { maxSum = currentMax; } else { maxSum = currentMaxSum; } } return maxSum; };
Complejidad
Complejidad temporal O(n) ya que se recorre el arreglo una sola vez. Complejidad espacial O(1) porque solo se usan variables escalares como maxSum y currentMax sin estructuras adicionales.
Sobre Q2BSTUDIO
Q2BSTUDIO es una empresa de desarrollo de software dedicada a crear aplicaciones a medida y software a medida para empresas de todos los tamaños. Somos especialistas en inteligencia artificial ia para empresas y agentes IA que automatizan procesos y mejoran la toma de decisiones. Además ofrecemos servicios de ciberseguridad para proteger infraestructuras y datos críticos, servicios cloud aws y azure para desplegar soluciones en la nube y servicios inteligencia de negocio que incluyen integración y visualización con power bi.
Nuestros servicios abarcan consultoría, diseño y desarrollo de aplicaciones a medida, implementación de modelos de inteligencia artificial, despliegue en servicios cloud aws y azure, soluciones de inteligencia de negocio y proyectos de ciberseguridad. Contacte con Q2BSTUDIO para potenciar su transformación digital con software a medida aplicaciones a medida inteligencia artificial ciberseguridad servicios cloud aws y azure servicios inteligencia de negocio agentes IA y power bi.
.jpg)