/*

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

*/

// http://en.wikipedia.org/wiki/Maximum_subarray_problem

// Kadane's Algorithm (1984)

// Dynamic Programming

// sum -- the max subarray sum ending at current value

// max -- the max subarray sum found so far

// In each day, we check the previous max, if max>0, we add current value to the subarray

// if max<0, we choose current day as a new starting point for subarray

// time: O(n); space: O(1)

public class Solution {

public int maxSubArray(int[] A) {

if (A==null || A.length==0) return 0;

int max = Integer.MIN_VALUE, sum = 0;

for (int i=0; i<A.length; i++){

// if sum+A[i] < A[i], we start a new subarray

sum = Math.max(A[i], sum+A[i]);

max = Math.max(sum, max);

}

return max;

}

}

// Divide and Conquer

// time: O(nlgn); space: O(1)

public class Solution {

public int maxSubArray(int[] A) {

if (A==null || A.length==0) return 0;

return finder(A, 0, A.length-1);

}

public int finder(int[] A, int start, int end){

if (start > end) return Integer.MIN_VALUE;

int mid = start + ((end - start)>>1); // notice here, cannot omit the out-nested brackets

int left=Integer.MIN_VALUE, right=Integer.MIN_VALUE, sum=0;

for (int i=mid+1; i<=end; i++){

sum += A[i];

right = Math.max(sum,right);

}

sum = 0;

for (int i=mid-1; i>=start; i--){

sum += A[i];

left = Math.max(sum, left);

}

int mmax = A[mid] + Math.max(left, 0) + Math.max(right, 0);

return Math.max(mmax, Math.max(finder(A, start, mid-1), finder(A, mid+1, end)));

}

}