I get that question from leet code and I got this answer from YouTube tutorial, but I don't understand the part of max. Because max is arr[0] and the value is -2, and even it goes inside of the loop, it is just -2 but max returns value 6.
How it possible?
const givenArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const getMax = arr => {
let sum = arr[0]; //-2
let max = arr[0]; //-2
for (let i = 1; i < arr.length; i++) {
sum = Math.max(sum + arr[i], arr[i]);
max = Math.max(max, sum);
}
console.log(sum);
console.log(max);
};
getMax(givenArray);max=-2 sum=-2
loop arr[1]=1: sum = max( -2 + 1, 1) = 1, max = max( sum=1 , max=-2 ) = 1
max=1 sum=1
loop arr[2]=-3: sum = max( 1 + -3, -3) = -2, max = max( sum=-2, max=1 ) = 1
max=1 sum=-2
loop arr[3]=4: sum = max( -3 + 4, 4) = 4, max = max( sum=4, max=1 ) = 4
max=4 sum=4
loop arr[4]=-1: sum = max( 4 + -1, -1) = 3, max = (3,4) = 4
max=4 sum=3
loop arr[5]=2: sum = max( 3 + 2, 2) = 5, max = max(5,4) = 5
So the iteration looks like this:
arr [-2, 1, -3, 4, -1, 2, 1, -5, 4] sum x, 1, x, 4, 3, 5, 6, 1, 5 max -2, 1, 1, 4, 4, 5, 6, 6, 6
It's like finding progressive sums, discarding negative sequences or starting off a new sequence when sum is negative, because any negative sequence would contribute negatively to the total sum of a sequence.
And, you use max = Math.max(max, sum), (set max to what's bigger, current max value or current sum) to find the largest value reached in the progressive sums (which is 6).
This also accounts for edge case of all negatives, where the maximal sum will be the largest negative number.
const givenArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const getMax = arr => {
let sum = arr[0]; //-2
let max = arr[0]; //-2
for (let i = 1; i < arr.length; i++) {
sum = Math.max(sum + arr[i], arr[i]);
max = Math.max(max, sum);
console.log(`max=${max}`, `sum=${sum}`);
}
};
getMax(givenArray);