Javascript算法最大子数组

Question

我从 leet 代码中得到了这个问题，我从 YouTube 教程中得到了这个答案，但我不明白 max 的部分。因为 max 是 arr[0] 而 value 是 -2，即使它进入循环内部，它只是 -2 但 max returns value 6.

怎么可能？

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

Answer 1

max=-2 sum=-2

循环 arr[1]=1: sum = max( -2 + 1, 1) = 1, max = max( sum=1 , max=-2 ) = 1

max=1 总和=1

循环arr[2]=-3: sum = max( 1 + -3, -3) = -2, max = max( sum=-2, max=1 ) = 1

max=1 总和=-2

循环 arr[3]=4: sum = max( -3 + 4, 4) = 4, max = max( sum=4, max=1 ) = 4

max=4 总和=4

循环 arr[4]=-1: sum = max( 4 + -1, -1) = 3, max = (3,4) = 4

max=4 总和=3

循环arr[5]=2: sum = max( 3 + 2, 2) = 5, max = max(5,4) = 5

所以迭代看起来像这样：

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

这就像找到累进和、丢弃负序列或在和为负时开始一个新序列，因为任何负序列都会对序列的总和产生负面影响。

并且，你使用max = Math.max(max, sum)，（将max设置为当前最大值或当前总和中较大的那个）来找到累进总和中达到的最大值（即6 ).
这也说明了所有负数的边缘情况，其中最大和将是最大的负数。

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

Javascript算法最大子数组

Javascript Algorithm Maximum subarray

javascript

arrays

algorithm

kadanes-algorithm