javaalgorithmkadanes-algorithm

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


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?


Solution

  • Something like this:

    public class Kadane {
      double[] maxSubarray(double[] a) {
        double max_so_far = a[0];
        double max_ending_here = a[0];
        int max_start_index = 0;
        int startIndex = 0;
        int max_end_index = -1;
    
        for(int i = 1; i < a.length; i++) {
          if(a[i] > max_ending_here +a[i]) {
            startIndex = i;
            max_ending_here = a[i];
          }
          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;
      }
    }
    

    UPDATE by the OP: also handle the cases with all negative numbers in the array and default of the sum is 0.