How to return maximum sub array in Kadane's al

问题:

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?

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

回答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

回答3:

I maintain the max_so_far in a list:

for(int i = 0;i<N;i++){
    max_end_here = Math.max(seq[i], max_end_here + seq[i]);
    sum_list.add(max_end_here);
    // System.out.println(max_end_here);
    max_so_far = Math.max(max_so_far, max_end_here);
}

Then search the biggest sum in list, its index as sub sequnece end. Start from index as end and search backwards, find the last index whose value is positive. Subsequence start is this index.

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

回答4:

A more easier approach closely linked to the algorithm.

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;i<size;i++)
   {
   max_so_far=max_so_far+a[i];//kadane's algorithm step 1
   if(max_so_far>max_sum) //computing max
   {
      max_sum=max_so_far;
      endIndex=i;
   }

   if(max_so_far<0)
   {
   max_so_far=0;
   startIndex=i+1;
   }
}
   cout<<max_so_far<<" "<<startIndex<<" "<<endIndex;
   getchar();
   return 0;
}

Once you have start and End index.

for(i=startIndex;i<=endIndex;i++)
{
cout<<a[i];
}

回答5:

we can keep track max subarray by using following code :

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

P.S. Assume that given array is candidate of Max sub array problem as well as not having all elements negative

回答6:

Update the probable left(starting) index every time a new sub-array sum is initiated. Update the final left and right(ending) once the max_sum is updated. Also maintain a trigger that tells if a new sub-array sum is created.

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