Maximal Subarray (Largest Continuous Sum)

Given an array, describe an algorithm to identify the subarray with the maximum sum.

For example, if the input is [1, ‐3, 5,‐2,9,‐8,‐6,4], the output would be [5,‐2,9].

Answer:Observe that the sum of a subarray from element i to element j is equal to the sum of the subarray from element
1 to element j minus the subarray from element 1 to element i‐1.Our algorithm will iterate through the array.The algorithm keeps track of the sum x of the elements no later than the element. It will also keep track of the minimum
sum y of the subarray from the first element to an element no later than the current element.

Finally,It will also keep track of the subarray z with the maximum sum so far.At each step,we update x by adding the current element to it. We update y by checking whether x < y; if so, we set y to be x.We update z by checking whether y‐x
is greater than z;if so, we set z to be y‐x.

For example,with the sample input, our algorithm would do the following:


     Current element     | x  | y  | z
--------------------------------------
            1            | 1  | 0  | 1
           -3            | -2 | -2 | 0
            5            | 3  | -2 | 5
           -2            | 1  | -2 | 5
            9            | 10 | -2 | 12
           -8            | 2  | -2 | 12
           -6            | -4 | -4 | 12
            4            | 0  | -4 | 12

Surprisingly,this problem is equivalent to the stock market problem. 

Given an array a1, you can "convert" it to an array a2 for the stock market problem by setting each element a2[i] to be 
a1[0]+ a1[1]+...+a1[i].


def max_subarray(A):
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Java Code : 

public class MaxSumSubArray {

 public static void main(String[] args) {
  int[] a = { 4, 5, 2, -6, 1, -9, 4, 2 };
  findMaxSumSubArray(a);
 }

 public static void findMaxSumSubArray(int a[]) {
  int size = a.length;
  if (size < 0)
   return;

  int maxSum = a[0];
  int maxStartIndex = 0;
  int maxEndIndex = 0;

  int curSum = a[0];
  int curStartIndex = 0;

  for (int i = 1; i < size; i++) {
   if (curSum < 0) {
    curSum = 0;
    curStartIndex = i;
   }

   curSum = curSum + a[i];
   if (curSum > maxSum) {
    maxSum = curSum;
    maxStartIndex = curStartIndex;
    maxEndIndex = i;
   }
  }

  System.out.println("Start index: " + maxStartIndex + " End index: "
    + maxEndIndex + " Max sum: " + maxSum);
 }
}

Refer : http://www.geeksforgeeks.org/archives/576