How to return maximum sub array in Kadane's algorithm?
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;
}
}
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.
SEE Kadane algorithm at http://en.wikipedia.org/wiki/Maximum_subarray_problem