Javascript算法最大子数组

小编典典

Javascript算法最大子数组

algorithm

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

阅读 354

2020-07-28

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

2020-07-28