0
503
ViewsSubarray máximo, no puedo entender cómo funciona el código
Hay una función que encuentra la suma más grande en un subarreglo
var maxSubArray = function(nums) { if(nums.length == 0) return 0; let result = Number.MIN_SAFE_INTEGER; let sum = 0; for(let i = 0; i < nums.length; i++) { sum += nums[i]; result = Math.max(sum, result); sum = sum < 0 ? 0 : sum; } return result; }; console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]));Pero no puedo entender qué está cambiando y por qué deja de funcionar si elimina la línea: 'resultado = Math.max (suma, resultado);'
Y cambie el resultado devuelto a la suma
3 answers
Answer question0
Esta es la implementación del Kadane's Algorithm para el Largest Sum Subarray .
La esencia del algo es:
No agregue un subarreglo que ya se está sumando a un número negativo. Esto solo disminuirá aún más la suma.
El resultado debe actualizarse cada vez que la suma de un subarreglo tenga un valor mayor que su valor actual
Por ejemplo : este es el resultado de agregar console.log en posiciones relevantes. 
Note: Here is the link where you can read more: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
0
Si comenta la línea de resultados, básicamente, la función no tendrá memoria de los "candidatos a la mejor suma" anteriores. Simplemente se ejecutará sobre la matriz agregando valores a la variable de sum , incluso cuando reduzca el valor de la suma (que no puede evitar y es útil solo si realiza un seguimiento de los mejores candidatos de suma anteriores).
Para explicarlo mejor, imagina que comentas esa línea y devuelves sum . Cada vez que la suma resulte ser negativa, se restablecerá inmediatamente a 0. Entonces, en el ejemplo propuesto, el subarreglo máximo final comenzará efectivamente a sumar en 4 y seguirá sumando si la sum total es mayor que cero INCLUSO si después de sumar el nuevo valor, la suma es menor que su valor anterior.
Así que básicamente será así:
[-2] // sum = -2. Less than 0, so reset to sum = 0 [-2, 1] // sum = 1 [-2, 1, -3] // sum = -2. Less than 0, so reset to sum = 0 [-2, 1, -3, 4] // sum = 4 [-2, 1, -3, 4, -1] // sum = 3 [-2, 1, -3, 4, -1, 2] // sum = 5 [-2, 1, -3, 4, -1, 2, 1] // sum = 6 BEST SUM [-2, 1, -3, 4, -1, 2, 1, -5] // sum = 1 :( [-2, 1, -3, 4, -1, 2, 1, -5, 4] // sum = 5 Es por eso que el result variable es necesario. Tienes que hacer un seguimiento de la mejor suma hasta el momento y compararla con el "mejor local", por así decirlo.
En el código original, el estado a lo largo de las iteraciones se vería así:
[-2] // sum = -2 // result = -2 because -2 is greater than Number.MIN_SAFE_INTEGER. // sum = 0. It gets reset because it's negative [-2, 1] // sum = 1 // result = 1 because 1 > -2 [-2, 1, -3] // sum = -2 // result = 1 and isn't updated because the overall max sum so far is greater than the current sum // sum = 0 [-2, 1, -3, 4] // sum = 4 // result = 4 [-2, 1, -3, 4, -1] // sum = 3 // result = 4 and isn't updated because the overall max sum is greater than the current sum [-2, 1, -3, 4, -1, 2] // sum = 5 // result = 5 [-2, 1, -3, 4, -1, 2, 1] // sum = 6 BEST SUM // result = 6 [-2, 1, -3, 4, -1, 2, 1, -5] // sum = 1 // result = 6 [-2, 1, -3, 4, -1, 2, 1, -5, 4] // sum = 5 // result = 6 Entonces, como puede ver, el valor final ahora es 6 porque la suma máxima general se conserva en la variable de result , mientras que la sum realiza un seguimiento de la mejor local.
0
Está agregando todos los elementos adyacentes para obtener un subarreglo con suma máxima.
En el ejemplo anterior, el subarreglo es [4,-1,2,1]
todos los demás subarreglos que tienen una suma menor que 6.