如何在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; } } 

上面的代码返回最大子数组的总和。

我怎样才能返回具有最大总和的子数组？

Answer 1

像这样的东西：

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

Answer 2

上面的代码有错误。 应该：

 max_ending_here = Math.max(a[i], max_ending_here + a[i]); 

不：

 max_ending_here = Math.max(0, max_ending_here + a[i]); 

如果不是，则会失败的序列如：2,4,22,19，-48，-5,20,40并返回55而不是60的正确答案。

在http://en.wikipedia.org/wiki/Maximum_subarray_problem上查看Kadane算法

Answer 3

我在列表中维护max_so_far：

 for(int i = 0;i 

然后搜索列表中的最大总和，其索引为子序列结束。 从索引作为结束开始并向后搜索，找到其值为正的最后一个索引。 子序列开始是这个索引。

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

Answer 4

一种与算法紧密相关的更简单的方法。

 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;imax_sum) //computing max { max_sum=max_so_far; endIndex=i; } if(max_so_far<0) { max_so_far=0; startIndex=i+1; } } cout< 

一旦你有开始和结束索引。

 for(i=startIndex;i<=endIndex;i++) { cout< 

Answer 5

我们可以使用以下代码跟踪最大子arrays：

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

PS假设给定数组是Max子arrays问题的候选者，并且没有所有元素都是负数

Answer 6

每次启动新的子arrays总和时，更新可能的左（起始）索引。 更新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; } }