Maximum Subarray

Problem Statement :

How to find the maximum sum of a sub array.
Example : for the array [1,2,-3,1] maximum sum possible is for the sub array [1,2] = 3.
                  for the array [10,5,-24,20,-1,35] maximum sum possible is for the sub array [20,-1,35]=54

Solution:  Kadane's Algorithm provides 0(n) solution to solve the problem. Kadane's algorithm keeps track of the maximum value of a sequence ending at the current point, and the maximum value seen so far.




Following Code sample demonstrates a method which can be used to find the maximum sub array.

public int getMaximumSubarray(int inputArray[]) {
  int max_ending_here = 0, max_so_far = 0;

  for (int i = 0; i < inputArray.length; i++) {
     max_ending_here = max(0, max_ending_here + inputArray[i]);
     max_so_far = max(max_so_far, max_ending_here);
  }
  return max_so_far;
 }