Kadane 的算法没有为最大的连续总和返回正确的值？

Question

尝试使用此处解释的 Kadane 算法：https://www.youtube.com/watch?v=OexQs_cYgAQ&t=721s

在这个数字数组中：[-5, 10, 2, -3, 5, 8, -20]。

答案是10 + 2 – 3 + 5 + 8 = 22

然而，当我运行下面的代码时，我得到了这个：

sumArray = [ 0, 20, 24, 24, 28, 44, 44 ]

不知道 24 和更高的数字是如何进入的:( 并且缺少 22。

代码如下：

const myArray = [-5, 10, 2, -3, 5, 8, -20];

const findMaxConsecutiveSum = (arr) => {
  const sumArray = [];
  let max_so_far = 0;
  let max_ending_here = 0;

  for (let i = 0; i < arr.length; i++) {
    max_ending_here = max_ending_here + arr[i];
    // console.log('position:', i, arr[i]);
    // console.log(max_ending_here = max_ending_here + arr[i]);
    // console.log('max_ending_here', max_ending_here);

    if (max_ending_here < 0) {
      max_ending_here = 0;
    }
    else if (max_so_far < max_ending_here) {
      max_so_far = max_ending_here;
    }

    // console.log('max_so_far', max_so_far);
    sumArray.push(max_so_far);
  }

  return sumArray;
}

console.log(findMaxConsecutiveSum(myArray));

我的想法是填充 sumArray 然后按最大数过滤它。但是我没有得到 22 而是一大堆更大的数字？

知道为什么吗？

Answer 1

您使实施变得比需要的复杂得多。从 Kadane's algorithm 的 post 开始，代码应如下所示：

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

那里所述的算法希望返回一个 单个数字 ，而不是一个数组。翻译成 JS，看起来像：

const myArray = [-5, 10, 2, -3, 5, 8, -20];
const findMaxConsecutiveSum = (arr) => {
  let max_so_far = 0;
  let max_ending_here = 0;
  for (let i = 0; i < arr.length; i++) {
    max_ending_here = Math.max(arr[i], max_ending_here + arr[i]);
    max_so_far = Math.max(max_so_far, max_ending_here)
  }
  return max_so_far;
}
console.log(findMaxConsecutiveSum(myArray));

请注意，max_ending_here 的重新分配需要在 arr[i] 和 max_ending_here + arr[i] 上调用 Math.max。

Answer 2

据我了解Kadane的算法（来自这个Wikipedia post），实现它的方式是这样的：

const myArray = [-5, 10, 2, -3, 5, 8, -20];
console.log(myArray.reduce((t, v) => { t.here = Math.max(v, v + t.here);
                                       t.max = Math.max(t.max, t.here); 
                                       return t; },
                           { here : 0, max : 0})['max']);

Kadane 的算法没有为最大的连续总和返回正确的值？

Kadane's Algorithm not returning correct value for largest consecutive sum?

javascript

arrays

algorithm

math

kadanes-algorithm