卡丹的算法解释道

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.

这个例子来自维基百科.

以下是维基百科在以下段落中给出的代码的翻译:"在整个数组由负数组成的情况下,不允许返回零长度子阵列的问题的变体可以用以下代码:"

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

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

Answer 2

这将处理混合数组和所有负数数组的情况.

var maximumSubArray = function(arr) {
    var max_cur=arr[0], max_global = arr[0];
    for (var i = 1; i < arr.length; i++) {
        max_cur = Math.max(arr[i], max_cur + arr[i]);
        max_global = Math.max(max_cur, max_global);
    }  
    return max_global;
};
console.log(maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maximumSubArray([-10, -11, -12]));