Javascript算法最大子数组 [英] Javascript Algorithm Maximum subarray

问题描述

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

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.

怎么可能?

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

max=-2 sum=-2

loop arr [1] = 1:sum = max(-2 + 1，1)= 1，max = max(sum = 1，max = -2)= 1

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

max = 1 sum = 1

max=1 sum=1

loop arr [2] =-3:sum = max(1 + -3，-3)= -2，max = max(sum = -2，max = 1)= 1

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

max = 1 sum = -2

max=1 sum=-2

loop arr [3] = 4:sum = max(-3 + 4，4)= 4，max = max(sum = 4，max = 1)= 4

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

max = 4 sum = 4

max=4 sum=4

loop arr [4] =-1:sum = max(4 + -1，-1)= 3，max =(3,4)= 4

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

max = 4 sum = 3

max=4 sum=3

loop arr [5] = 2:sum = max(3 + 2，2)= 5，max = max(5,4)= 5

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.

然后，您使用max = Math.max(max，sum)，(将max设置为更大的值，当前最大值或当前总和)来找到渐进总和中达到的最大值(为6). > 这也说明了所有负数的边缘情况，其中最大和为最大负数.

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

这篇关于Javascript算法最大子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！