/**
 * http://www.geeksforgeeks.org/?p=576
 */
package com.g4g.arrays;

/**
 * @author Kushal
 *
 */
public class MaxSumContiguousArray {

  /**
   * Kadane's algo for finding the max sub array sum.
   *
   * @param arr
   * @param len
   * @return
   */
  public static int calMaxSumArray(int[] arr, int len) {
    int maxSoFar = 0, currMax = 0;
    int start = 0, end = 0, tmp = 0;

    for (int i = 0; i <= len; i++) {
      currMax += arr[i];
      if (currMax > maxSoFar) {
        maxSoFar = currMax;
        start = tmp;
        end = i;
      }
      if (currMax < 0) {
        tmp = i + 1;
        currMax = 0;
      }
    }
    System.out.println("start = " + start + " end = " + end);
    return maxSoFar;
  }

  /**
   * Method to handle if all elements are -ve
   *
   * @param arr
   * @param len
   * @return
   */
  public static int calMaxSum(int[] arr, int len) {
    int currSum = arr[0];
    int maxSoFar = arr[0];

    for (int i = 0; i <= len; i++) {
      currSum = Math.max(arr[i], arr[i] + currSum);
      maxSoFar = Math.max(currSum, maxSoFar);
    }
    return maxSoFar;
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    int arr[] = {-2, -3, -4, -1, -2, -1, -5, -3};
    System.out.println("Max Sum = " + calMaxSumArray(arr, arr.length - 1));
  }

}
