javascript - Javascript算法最大子数组

Question

我从 leet 代码中得到了这个问题，我从 YouTube 教程中得到了这个答案，但我不明白 max 的部分。因为 max 是arr[0]并且 value 是-2，即使它进入循环内部，它也只是-2max 返回 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);

标签： javascriptarraysalgorithmkadanes-algorithm

Answer 1

最大值=-2 总和=-2

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

最大=1 总和=1

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

最大值=1 总和=-2

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

最大=4 总和=4

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

最大=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]  
总和 x, 1, x, 4, 3, 5, 6, 1, 5  

最大值 -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);