java 如何在 Kadane 算法中返回最大子数组？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7778186/
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
How to return maximum sub array in Kadane's algorithm?
提问by Aqib Saeed
public class Kadane {
double maxSubarray(double[] a) {
double max_so_far = 0;
double max_ending_here = 0;
for(int i = 0; i < a.length; i++) {
max_ending_here = Math.max(0, max_ending_here + a[i]);
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
}
The above code returns the sum of the maximum sub-array.
上面的代码返回最大子数组的总和。
How would I instead return the sub-array which has the maximum sum?
我将如何返回具有最大总和的子数组？
回答by mikey
Something like this:
像这样的东西：
public class Kadane {
double[] maxSubarray(double[] a) {
double max_so_far = 0;
double max_ending_here = 0;
int max_start_index = 0;
int startIndex = 0;
int max_end_index = -1;
for(int i = 0; i < a.length; i++) {
if(0 > max_ending_here +a[i]) {
startIndex = i+1;
max_ending_here = 0;
}
else {
max_ending_here += a[i];
}
if(max_ending_here > max_so_far) {
max_so_far = max_ending_here;
max_start_index = startIndex;
max_end_index = i;
}
}
if(max_start_index <= max_end_index) {
return Arrays.copyOfRange(a, max_start_index, max_end_index+1);
}
return null;
}
}
回答by Andy
The code above has an error. Should be:
上面的代码有错误。应该：
max_ending_here = Math.max(a[i], max_ending_here + a[i]);
NOT:
不是：
max_ending_here = Math.max(0, max_ending_here + a[i]);
If not, would fail for a sequence such as: 2 , 4, 22, 19, -48, -5 , 20, 40 and return 55 instead of the correct answer of 60.
如果不是，则会失败，例如： 2 , 4, 22, 19, -48, -5 , 20, 40 并返回 55 而不是正确答案 60。
SEE Kadane algorithm at http://en.wikipedia.org/wiki/Maximum_subarray_problem
请参阅http://en.wikipedia.org/wiki/Maximum_subarray_problem 上的Kadane 算法
回答by nathanlrf
I maintain the max_so_far in a list:
我在列表中维护 max_so_far：
for(int i = 0;i<N;i++){
max_end_here = Math.max(seq[i], max_end_here + seq[i]);
sum_list.add(max_end_here);
// System.out.println(max_end_here);
max_so_far = Math.max(max_so_far, max_end_here);
}
Then search the biggest sum in list, its index as sub sequnece end. Start from index as end and search backwards, find the last index whose value is positive. Subsequence start is this index.
然后搜索列表中最大的和，其索引作为子序列的结尾。从索引开始，向后搜索，找到最后一个值为正的索引。后续开始就是这个索引。
for(int i=sum_list.size()-1; i>=0; i--){
if(sum_list.get(i) == max_so_far){
end = i;
while(sum_list.get(i) > 0 && i>=0){
i--;
}
start = (i==-1)?0:i+1;
break;
}
}
回答by Saras Arya
A more easier approach closely linked to the algorithm.
一种与算法密切相关的更简单的方法。
int main()
{
int a[]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
int size=sizeof(a)/sizeof(a[0]);
int startIndex=0,endIndex=0,i,j;
int max_so_far=0,max_sum=-999;
for(i=0;i<size;i++)
{
max_so_far=max_so_far+a[i];//kadane's algorithm step 1
if(max_so_far>max_sum) //computing max
{
max_sum=max_so_far;
endIndex=i;
}
if(max_so_far<0)
{
max_so_far=0;
startIndex=i+1;
}
}
cout<<max_so_far<<" "<<startIndex<<" "<<endIndex;
getchar();
return 0;
}
Once you have start and End index.
一旦你有了开始和结束索引。
for(i=startIndex;i<=endIndex;i++)
{
cout<<a[i];
}
回答by optional
we can keep track max subarray by using following code :
我们可以使用以下代码跟踪最大子数组：
import java.util.Arrays;
public class KadaneSolution4MaxSubArray{
public static void main(String[]args){
int [] array = new int[]{13,-3,-25,20 ,-3 ,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
int[] maxSubArray = maxSubArrayUsingKadaneSol(array);
for(int e : maxSubArray){
System.out.print(e+"\t");
}
System.out.println();
}
public static int[] maxSubArrayUsingKadaneSol(int array[]){
long maxSoFar =array[0];
long maxEndingHere =array[0];
int startIndex = 0;
int endIndex =0;
int j=1;
for(; j< array.length ;j++){
int val = array[j];
if(val >= val+maxEndingHere){
maxEndingHere = val;
startIndex = j;
}else {
maxEndingHere += val;
};
if(maxSoFar < maxEndingHere){
maxSoFar = maxEndingHere;
endIndex = j;
}
}
return Arrays.copyOfRange(array,startIndex,endIndex+1);
}
}
P.S. Assume that given array is candidate of Max sub array problem as well as not having all elements negative
PS 假设给定的数组是最大子数组问题的候选者，并且没有所有元素都是负数
回答by Kushal Mondal
Update the probable left(starting) index every time a new sub-array sum is initiated. Update the final left and right(ending) once the max_sum is updated. Also maintain a trigger that tells if a new sub-array sum is created.
每次启动新的子数组和时，更新可能的左（起始）索引。一旦 max_sum 更新，更新最后的左右（结尾）。还维护一个触发器，告知是否创建了新的子数组和。
int last = 0;
int sum = Integer.MIN_VALUE;
boolean fOrReset = true;
int _L = -1, L = -1, R = -1;
for (int j = 0; j < arr.length; j++) {
last += arr[j];
if (fOrReset) {
_L = j+1;
}
fOrReset = false;
if (sum < last) {
sum = last;
L = _L;
R = j+1;
}
if (last < 0) {
last = 0;
fOrReset = true;
}
}
回答by javaProf
private static int[] applyKadaneAlgorithmGetSubarrayOptimized(int[] input) {
int localMax = input[0];
int globalMax = input[0];
int start = 0;
int end = 0;
for (int i = 1; i < input.length; i++) {
localMax = Math.max(localMax + input[i], input[i]);
if(localMax == input[i]) { //this is similar as --> input[i] > (localMax + input[i])
start = i;
}
if(localMax > globalMax) {
end = i;
}
globalMax = Math.max(localMax, globalMax);
}
//Below condition only occur`enter code here`s when all members of the array are negative integers
//Example: {-9, -10, -6, -7, -8, -1, -2, -4}
if(start > end) {
start = end;
}
return Arrays.copyOfRange(input, start, end + 1);
}
