喵喵~: Maximum subarray@leetcode

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.

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
Kadane’s Algorithm:

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

DP: Using extra O(n) space, Code from http://www.programcreek.com/2013/02/leetcode-maximum-subarray-java/

public int maxSubArray(int[] A) {
  int max = A[0];
  int[] sum = new int[A.length];
  sum[0] = A[0];
 
  for (int i = 1; i < A.length; i++) {
   sum[i] = Math.max(A[i], sum[i - 1] + A[i]);
   max = Math.max(max, sum[i]);
  }
 
  return max;
}

Dive and Conquer: O(nlogn)
int maxSubArray(int A[], int n) {
  // Start typing your C/C++ solution below
  // DO NOT write int main() function
  int maxV = INT_MIN;
  return maxArray(A, 0, n-1, maxV);    
}
int maxArray(int A[], int left, int right, int& maxV)
{
  if(left>right)
return INT_MIN;
  int mid = (left+right)/2;
  int lmax = maxArray(A, left, mid -1, maxV);
  int rmax = maxArray(A, mid + 1, right, maxV);
  maxV = max(maxV, lmax);
  maxV = max(maxV, rmax);
  int sum = 0, mlmax = 0;
  for(int i= mid -1; i>=left; i--)
  {
sum += A[i];
if(sum > mlmax)
 mlmax = sum;
  }
  sum = 0; int mrmax = 0;
  for(int i = mid +1; i<=right; i++)
  {
sum += A[i];
if(sum > mrmax)
 mrmax = sum;
  }
  maxV = max(maxV, mlmax + mrmax + A[mid]);
  return maxV;
}
Read full article from 喵喵~: Maximum subarray@leetcode