Maximum Subarray解题报告zz

http://fisherlei.blogspot.com/2012/12/leetcode-maximum-subarray.html

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.
假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值，定义为Max[i], 在这里，当求取Max[i+1]时，
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]必为负数，没必要保留，舍弃掉
然后从左往右扫描，求取Max数字的最大值即为所求。

[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:    }

但是题目中要求，不要用这个O(n)解法，而是采用Divide & Conquer。这就暗示了，解法必然是二分。分析如下：

假设数组A[left, right]存在最大值区间[i, j](i>=left & j<=right)，以mid = (left + right)/2 分界，无非以下三种情况：

subarray A[i,..j] is
(1) Entirely in A[low,mid-1]
(2) Entirely in A[mid+1,high]
(3) Across mid
对于(1) and (2)，直接递归求解即可，对于(3)，则需要以min为中心，向左及向右扫描求最大值，意味着在A[left, Mid]区间中找出A[i..mid], 而在A[mid+1, right]中找出A[mid+1..j]，两者加和即为(3)的解。

代码实现如下：

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:    }

[注意]
考虑到最大和仍然可能是负数，所以对于有些变量的初始化不能为0，要为INT_MIN。

巴特西

Maximum Subarray解题报告zz

http://fisherlei.blogspot.com/2012/12/leetcode-maximum-subarray.html

最新文章

热门文章