javascript Kadane 的算法解释
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32367032/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Kadane's algorithm explained
提问by devdropper87
Could someone take me through what is happening here in Kadane's algorithm? Wanted to check my understanding. here's how I see it.
有人可以带我了解 Kadane 算法中发生的事情吗？想检查一下我的理解。这就是我的看法。
you are looping through the array, and each time you set the ans variable to the largest value seen, until that value becomes negative, then ans becomes zero.
您正在遍历数组，每次将 ans 变量设置为所见的最大值，直到该值变为负数，然后 ans 变为零。
At the same time, the sum variable is overwritten each time through the loop, to the max between previously seen sums or the largest 'ans' so far. Once the loop is finished executing you will have the largest sum or answer seen so far!
同时，每次通过循环都会覆盖 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;
};
回答by Dan D.
Consider tracing the values:
考虑跟踪值：
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]);
Prints:
印刷：
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
The first column is ans, which is the sum of the current subarray. The second is sum, representing the sum of the greatest seen so far. The third is the element that was just visited. You can see that the contiguous subarray with the largest sum is 4, ?1, 2, 1, with sum 6.
第一列是ans，它是当前子数组的总和。第二个是sum，代表迄今为止所见最大的总和。第三个是刚刚访问过的元素。可以看到总和最大的连续子数组是4, ?1, 2, 1，和6。
The example is from Wikipedia.
这个例子来自维基百科。
The following is a translation of the code given in Wikipedia under the paragraph: "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:" [EDIT: Small bug fixed in the code below]
以下是维基百科段落下给出的代码的翻译：“不允许返回零长度子数组的问题的变体，在整个数组由负数组成的情况下，可以用以下代码：” [编辑：在下面的代码中修复了小错误]
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;
};
See that:
看到：
> maximumSubArray([-10, -11, -12])
-10 -10
-10 -10 -11
-10 -10 -12
-10 -10
-10
The last number is the expected result. The others are as in the previous example.
最后一个数字是预期的结果。其他的和前面的例子一样。
回答by Vinayak Sakhare
This will take care of both situations mixed array and all negative number array.
这将处理混合数组和所有负数数组的两种情况。
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]));回答by akashrajkn
look at this link, it gives a clear explanation for Kadane's algorithm.
看看这个链接，它对 Kadane 的算法给出了清晰的解释。
Basically you have to look for all positive contiguous segments of the array and also keep track of the maximum sum contiguous segment until the end. Whenever you find a new positive contiguous segment, it checks if the current sum is greater than the max_sumso far and updates that accordingly.
基本上，您必须查找数组的所有正连续段，并跟踪最大和连续段直到结束。每当您找到一个新的正连续段时，它都会检查当前总和是否大于目前的总和max_sum并相应地更新它。
The following code handles the case when all the numbers are negative.
以下代码处理所有数字均为负数的情况。
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;
}
回答by amoljdv06
I have done enhacement to Kadane's Algorithm for all negative number in an array as well.
我也对数组中的所有负数进行了 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;
}
Test Case: -30 -20 -10
测试用例：-30 -20 -10
-10
-10
-10 -20 -30
-10 -20 -30
-10
-10
-2 -3 4 -1 -2 1 5 -3
-2 -3 4 -1 -2 1 5 -3
7
7
回答by 28rox
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;
}
}
回答by Mihey Mik
I would prefer a more functional way in JavaScript:
我更喜欢 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
