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.

click to show more practice.

解题思路：

题意为找出连续的和最大的子数组的和。可以有两种方法来做，动态规划以及分治法。

1、动态规划。求最值问题一般可以考虑动态规划的方法。d[i]表示子数组nums[k, i]的最大值，其中k>=0并且k

d[i] = nums[i], i==0 或者 d[i-1]<0
d[i] = nums[i] + d[i-1], 其他

然后返回d[]数组的最大值即可。这种方法的空间复杂度为O(n)，其实可以优化成O(1)的空间复杂度。时间复杂度为O(n)

class Solution {
public:
    int maxSubArray(vector
  
   & nums) {
        int len = nums.size();
        if(len<1){
            return 0;
        }
        int d[len];
        d[0]=nums[0];
        int maxSum=nums[0];
        
        for(int i=1; i
   
    0){ d[i]=nums[i]+d[i-1]; }else{ d[i]=nums[i]; } maxSum = max(d[i], maxSum); } return maxSum; } };
   
  

（1）最大值子数组在mid前面

（2）最大值子数组在mid后边

（3）最大值子数组跨过mid

对于（1）（2），可以直接用递归来求得，对于（3），我们以mid向两边延伸找到最大的和。然后返回三种情况最大的一项即可。

空间复杂度为O(1)，时间复杂度为O(n)

class Solution {
public:
    int maxSubArray(vector
  
   & nums) {
        return maxSub(nums, 0, nums.size() - 1);
    }
    
    int maxSub(vector
   
    & nums, int left, int right){ if(left>right){ return INT_MIN; } int mid = (left + right) / 2; int lMax = maxSub(nums, left, mid - 1); int rMax = maxSub(nums, mid + 1, right); int sum = 0; int lMaxSub = 0; for(int i=mid - 1; i>=left; i--){ sum += nums[i]; lMaxSub = max(sum, lMaxSub); } int rMaxSub = 0; sum = 0; for(int i=mid + 1; i<=right; i++){ sum += nums[i]; rMaxSub = max(sum, rMaxSub); } return max(max(lMax, rMax), lMaxSub + rMaxSub + nums[mid]); } };