Encuentre el subarreglo contiguo dentro de un arreglo (que contenga al menos un número) que tenga la suma más grande.
Por ejemplo, dada la matriz [−2,1,−3,4,−1,2,1,−5,4], el subarreglo contiguo [4,−1,2,1] tiene la mayor suma = 6.
Solución de Java – DP
La forma más sencilla de formular la solución de este problema es mediante DP. Sea f (n) el subarreglo máximo para un arreglo con n elementos. Necesitamos encontrar el subproblema y la relación.
f(n) = { f(n-1)>0 ? f(n-1) : 0 } + nums[n-1]
f(0) = 0
f(1) = nums[0]
La condición para cambiar la programación dinámica es «que debemos ignorar la suma de los n-1 elementos anteriores si enésimo elemento es mayor que la suma».
public int maxSubArray(int[] nums) { int result = nums[0]; int[] sum = new int[nums.length]; sum[0] = nums[0]; for(int i=1; i<nums.length; i++){ sum[i] = Math.max(nums[i], sum[i-1] + nums[i]); result = Math.max(result, sum[i]); } return result; } |
La complejidad del tiempo y la complejidad del espacio son las mismas O (n). Sin embargo, podemos mejorar la complejidad del espacio y convertirlo en O (1).
public int maxSubArray(int[] nums) { int result = nums[0]; int sum = nums[0]; for(int i=1; i<nums.length; i++){ sum = Math.max(nums[i], sum + nums[i]); result = Math.max(result, sum); } return result; } |
