javascript - Kadane 的算法解释

Question

有人可以告诉我 Kadane 算法中发生了什么吗？想检查我的理解。这就是我的看法。

你正在遍历数组，每次将 ans 变量设置为看到的最大值，直到该值变为负数，然后 ans 变为零。

与此同时，每次循环都会覆盖 sum 变量，直到之前看到的总和之间的最大值或迄今为止最大的“ans”。循环执行完毕后，您将获得迄今为止看到的最大总和或答案!

var sumArray = function(array) {
      var ans = 0;
      var sum = 0;
      //loop through the array.


      for (var i = 0; i < array.length; i++) {
        //this is to make sure that the sum is not negative. 
        ans = Math.max(0, ans + array[i]);

        //set the sum to be overwritten if something greater appears.
        sum = Math.max(sum, ans)
      }

      return sum;

    };

Answer 1

考虑跟踪值:

var maximumSubArray = function(array) {
    var ans = 0;
    var sum = 0;

    console.log(ans, sum);
    for (var i = 0; i < array.length; i++) {

        ans = Math.max(0, ans + array[i]);
        sum = Math.max(sum, ans);
        console.log(ans, sum, array[i]);
    }
    console.log(ans, sum);
    return sum;

};

maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]);

打印:

0 0
0 0 -2
1 1 1
0 1 -3
4 4 4
3 4 -1
5 5 2
6 6 1
1 6 -5
5 6 4
5 6

第一列是ans，是当前子数组的和。第二个是sum，代表目前看到的最大的总和。第三个是刚刚访问过的元素。可以看到和最大的连续子数组是4, −1, 2, 1，和6。

例子来自Wikipedia .

下面是一段维基百科中给出的代码的翻译:“不允许返回零长度子数组的问题的变体，在整个数组由负数组成的情况下，可以是使用以下代码解决:“[编辑:以下代码中修复的小错误]

var maximumSubArray = function(array) {
    var ans = array[0];
    var sum = array[0];

    console.log(ans, sum);
    for (var i = 1; i < array.length; i++) {

        ans = Math.max(array[i], ans + array[i]);
        sum = Math.max(sum, ans);
        console.log(ans, sum, array[i]);
    }
    console.log(ans, sum);
    return sum;

};

看到那个:

> maximumSubArray([-10, -11, -12])
-10 -10
-10 -10 -11
-10 -10 -12
-10 -10
-10

最后一个数字是预期结果。其他的和前面的例子一样。