喵喵~: 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.

int maxSubArray(int A[], int n) {

       

        int sum = 0, max = INT_MIN;

        for(int i=0; i<n; i++){

            sum+=A[i];

            if(sum>max) 

                max = sum;

            if(sum<0)

                sum = 0;

        }

            return max;

        }

    };

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