## Tuesday, December 25, 2012

### [LeetCode] Maximum Subarray 解题报告

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.
» Solve this problem

[解题思路]
O(n)就是一维DP.

Max[i+1] = Max[i] + A[i+1],  if (Max[i] + A[i+1] >0)
= 0, if(Max[i]+A[i+1] <0)，如果和小于零，A[i+1]必为负数，没必要保留，舍弃掉

[Code]
``````1:    int maxSubArray(int A[], int n) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int sum = 0;
5:      int max = INT_MIN;
6:      for(int i =0; i < n ; i ++)
7:      {
8:        sum +=A[i];
9:        if(sum>max)
10:          max = sum;
11:        if(sum < 0)
12:          sum = 0;
13:      }
14:      return max;
15:    }
``````

subarray A[i,..j] is
(1) Entirely in A[low,mid-1]
(2) Entirely in A[mid+1,high]
(3) Across mid

``````1:    int maxSubArray(int A[], int n) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int maxV = INT_MIN;
5:      return maxArray(A, 0, n-1, maxV);
6:    }
7:    int maxArray(int A[], int left, int right, int& maxV)
8:    {
9:      if(left>right)
10:        return INT_MIN;
11:      int mid = (left+right)/2;
12:      int lmax = maxArray(A, left, mid -1, maxV);
13:      int rmax = maxArray(A, mid + 1, right, maxV);
14:      maxV = max(maxV, lmax);
15:      maxV = max(maxV, rmax);
16:      int sum = 0, mlmax = 0;
17:      for(int i= mid -1; i>=left; i--)
18:      {
19:        sum += A[i];
20:        if(sum > mlmax)
21:          mlmax = sum;
22:      }
23:      sum = 0; int mrmax = 0;
24:      for(int i = mid +1; i<=right; i++)
25:      {
26:        sum += A[i];
27:        if(sum > mrmax)
28:          mrmax = sum;
29:      }
30:      maxV = max(maxV, mlmax + mrmax + A[mid]);
31:      return maxV;
32:    }
``````

[注意]