Javascript Algorithm Maximum subarray

Question

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);

"and even it goes inside of the loop, it is just -2" but it's overwritten within the loop, it doesn't stay -2 forever? — VLAZ
– VLAZ, Commented May 29, 2020 at 22:46
@VLAZ if I console.log(max) inside of for loop it only shows -2, for 9times — jenny
– jenny, Commented May 29, 2020 at 22:49
max = Math.max(max, sum) assigns a new value on each iteration. It will only keep the same value if max is always equal to or larger than sum from the beginning. — RobG
– RobG, Commented May 29, 2020 at 22:58
As a tangential side note, this is an exceptional level of patience for a Javascript question on Stack Overflow, props to both of you VLAZ and RobG. — Etheryte
– Etheryte, Commented May 29, 2020 at 23:08

user120242 · Accepted Answer · 2020-05-30 00:25:21Z

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);

Collectives™ on Stack Overflow

Javascript Algorithm Maximum subarray

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related