19

有人可以带我了解 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;

    };
4

6 回答 6

19

考虑跟踪值：

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, 和 sum 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

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

于 2015-09-03T04:57:11.143 回答
6

这将同时处理混合数组和所有负数数组的情况。

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

于 2017-07-11T19:37:43.413 回答
4

看看这个链接，它对 Kadane 的算法给出了清晰的解释。

基本上，您必须查找数组的所有正连续段，并跟踪最大和连续段直到结束。每当您找到一个新的正连续段时，它都会检查当前总和是否大于max_sum到目前为止的总和并相应地更新。

以下代码处理所有数字均为负数的情况。

int maxSubArray(int a[], int size)
{
   int max_so_far = a[0], i;
   int curr_max = a[0];

   for (i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}
于 2015-09-03T04:53:10.507 回答
1

对于数组中的所有负数，我也对 Kadane 算法进行了增强。

int maximumSubSum(int[] array){
        int currMax =0;
        int maxSum = 0;

        //To handle All negative numbers
        int max = array[0];
        boolean flag = true;
        for (int i = 0; i < array.length; i++) {

             //To handle All negative numbers to get at least one positive number
            if(array[i]<0)
                max= Math.max(max , array[i]);
            else
                flag = false;


            currMax = Math.max(0, currMax + array[i]);
            maxSum = Math.max(maxSum , currMax);
        }
        return flag?max:sum;
    }

测试用例：-30 -20 -10

-10

-10 -20 -30

-10

-2 -3 4 -1 -2 1 5 -3

7

于 2017-08-23T06:54:36.623 回答
0 
    import java.io.*;  
import java.util.*; 

class Main 
{ 
    public static void main (String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();    //size
        int a[]=new int[n];     //array of size n
        int i;
        for(i=0;i<n;i++)
        {
            a[i]=sc.nextInt();   //array input
        }

       System.out.println("Largest Sum Contiguous Subarray using Kadane’s Algorithm"+Sum(a));
    }

        static int Sum(int a[]) 
{ 

    int max = Integer.MIN_VALUE, max_ending = 0; 

    for (int i = 0; i < size; i++) 
    { 
        max_ending_here = max_ending + a[i]; 
        if (max < max_ending) 
            max = max_ending; //updating value of max
        if (max_ending < 0) 
            max_ending= 0; 
    } 
    return max; 
} 
        }
于 2019-07-24T03:56:14.560 回答
-2

我更喜欢 JavaScript 中更实用的方式：

const maximumSubArray = function(array) {
  return array.reduce(([acc, ans], x, i) => { 
    ans = Math.max(0, ans + x);
    return [Math.max(acc, ans), ans];
  }, [array[0],array[0]])[0];
};

cl(maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
于 2017-05-14T13:06:15.537 回答