How to return maximum sub array in Kadane's algorithm?

Question

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?

Answer 1

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

Answer 2

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