如何返回最大子阵列中的Kadane的算法? [英] How to return maximum sub array in Kadane's algorithm?
本文介绍了如何返回最大子阵列中的Kadane的算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
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;
}
}
以上code返回最大子阵列的总和。
The above code returns the sum of the maximum sub-array.
我将如何,而不是返回子阵列具有最大一笔?
How would I instead return the sub-array which has the maximum sum?
推荐答案
事情是这样的:
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;
}
}
这篇关于如何返回最大子阵列中的Kadane的算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文