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

看this link，卡丹的算法解释的很清楚

基本上，您必须查找数组的所有正连续段，并跟踪最大和连续段直到结束。每当您找到一个新的正连续段时，它会检查当前总和是否大于 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;
}

Answer 2

考虑追踪值：

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

打印：

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

示例来自Wikipedia.

以下是维基百科中该段给出的代码的翻译："A variation of the problem that does not allow zero-length subarrays to be returned, in the case that the entire array consists of negative numbers, can be solved with the following code:" [编辑：修复了以下代码中的小错误]

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 3

我更喜欢 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

Answer 4

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

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

Answer 5

我也对数组中所有负数的 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

Answer 6

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

Kadane 的算法解释

Kadane's algorithm explained

javascript

algorithm

kadanes-algorithm