0
496
VisualizaçõesMaximum Subarray, i can't understand how the code works
There is a function that finds the largest sum in a subarray
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]));
But I cannot understand what is changing and why it stops working if you remove the line: 'result = Math.max(sum, result);'
And change return result to sum
3 Respostas
Responde à pergunta0
This is the implementation of Kadane's Algorithm for Largest Sum Subarray.
The gist of the algo is:
Don't add a subarray which is already summing up to a negative number. This will only decrease the sum further.
Result has to be updated everytime with a subarray's sum having value more than it's current value
For example: This is the output of adding console.log at relevant positions.
Note: Here is the link where you can read more: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
0
If you comment the result line basically the function won't have memory of previous "candidates to best sum". It will just run over the array adding values to the sum variable, even when it lowers the value of the sum (which you can't avoid and it's useful only if you keep track of the previous best sum candidates).
To further explain, imagine you comment that line and return sum.
Every time the sum turns out to be negative it will be immediately reset to 0. So in your proposed example the final max subarray will be effectively starting to sum up on 4 an will keep summing up if the total sum is greater than zero EVEN if after adding the new value the sum is less than its previous value.
So basically it will go like this:
[-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
That's why the variable result is necessary. You have to keep track of the best sum so far and compare it with the "local best", so to speak.
In the original code the state throughout the iterations would look something like this:
[-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
So as you can see, the final value is now 6 because the overall max sum is persisted in the result variable while sum keeps track of the local best.
0
It is adding all adjacent elements to get subarray with maximum sum.
In above example the subarray is [4,-1,2,1]
all other subarrays having sum smaller than 6.