题目

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.

分析

题目要求O(n)的算法，然而dp对我来说就是老大难，想了半天的我看到题目属于Easy的时候内心是崩溃的=_=。我觉得dp的关键在于找到具有无后效性的量。一开始我考虑使用dp[i]来表示前i-1个数字中答案，但是始终找不到推导方法。后来转念一想，如果dp[i]表示以nums[i]为结尾的数字串的最大的和，就能够简答得到推导了。然后再输出dp数组中的最大值即可。

实现一

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        int dp[nums.size()];
        dp[0] = nums[0];
        for(int i=1; i<nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
        }
        int ans=INT_MIN;
        for(int i=0; i<nums.size(); i++){
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

思考一

这道Easy的题想了好久，看来dp的路对我来说还是很漫长啊。而且发现了这道题有可以改进的地方：不需要使用dp数组保存每个位置的值，因为每次只用到了最后一个。所以可以只使用一个变量，降低空间复杂度。
另外题目还说要用分治法来完成。关键问题在于如何将两个区域归并。这个问题我看的题解上没有解决，其它选手的代码中好像也找不到使用分治法的。后来网上搜了一下，明白了：

两个区域合并时，只需要考虑跨越两个区域的子数组即可。这样只需要连接左边区域的以最后一个元素为结尾的最大子数组，以及右边区域的以第一个元素为开头的最大子数组即可（如果子数组的和为正的话）

实现二

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return solve(nums, 0, nums.size()-1);
    }
private:
    int solve(vector<int>& nums, int start, int end){
        if(start>=end) return nums[start];
        int mid = (start + end) / 2;
        int lm = solve(nums, start, mid-1);
        int rm = solve(nums, mid+1, end);
        int mm = nums[mid];
        int mm1 = INT_MIN, t = 0;
        for(int i=mid-1; i>=start; i--){
            t += nums[i];
            mm1 = max(mm1, t);
        }
        mm += mm1>0 ? mm1 : 0;
        int mm2 = INT_MIN; t = 0;
        for(int i=mid+1; i<=end; i++){
            t += nums[i];
            mm2 = max(mm2, t);
        }
        mm += mm2>0 ? mm2 : 0;
        return max(lm, max(mm, rm));
    }
};