程序员面试金典 - 面试题 16.17. 连续数列（DP/分治）

示例：
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

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

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    	int maxSum = nums[0], dp_i_1 = nums[0], dp_i;
    	for(int i = 1; i < nums.size(); ++i)
    	{
			dp_i = max(nums[i], nums[i]+dp_i_1);
			maxSum = max(maxSum, dp_i);
			dp_i_1 = dp_i;
    	}
    	return maxSum;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    	return divide(nums,0,nums.size()-1);
    }

    int divide(vector<int>& nums, int l, int r)
    {
    	if(l == r)
    		return nums[l];
    	int i, mid = l+((r-l)>>1);
    	int Lsum = divide(nums,l,mid);//分治
    	int Rsum = divide(nums,mid+1,r);
    	//合并
    	int Ls = 0, Rs = 0, maxL = INT_MIN, maxR = INT_MIN;
    	for(i = mid; i >= 0; --i)//必须从中间开始遍历，便于求跨在两侧的最大和
    	{
    		Ls += nums[i];//左侧的和
    		maxL = max(maxL, Ls);//最大的左侧和
    	}
    	for(i = mid+1; i <= r; ++i)
    	{
    		Rs += nums[i];//右侧和
    		maxR = max(maxR, Rs);//最大的右侧和
    	}
    	return max(maxL+maxR, max(Lsum,Rsum));
    	//        最大的左+右和，最大的左侧和，最大的右侧和
    }
};