LeetCode 53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
解析：
给定一个数组，计算最大的连续子数组之和，返回最大的的和。
一维动态规划算法，在从头开始遍历的过程中，对每一个当前元素nums[i]，要么在原来的基础之上加上当前元素，要么从当前元素重新开始。
定义子问题：dp[i]为以第i个元素结尾的最大连续子数组和，很显然在for循环遍历的过程中，只有两种情况：
1）dp[i]重新以当前元素nums[i]开始；
2）dp[i]继续累加，即当前元素nums[i]+dp[i-1]；
对第i个元素来说，它的值取决于dp[i-1]，如果dp[i-1]是负数，那就没有必要加上它，因为这只会拖累子序列的最大和。如果是正数就加上它。最后我们再将第i个元素自身加进去，就得到了第i个元素之前最大的子序列和。

另外，dp[i]表示以i元素结尾的最大数组和，即必须包括i元素，所以需要数值max_sum来记录每个阶段的结果，选择每个子问题结果中的最大值。
具体看代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len);
        dp[0] = nums[0];
        int max_sum = nums[0];
        for(int i=1; i< len; i++)
        { 
            int temp = dp[i-1] + nums[i];
            dp[i] = temp>nums[i]?dp[i-1] + nums[i]:nums[i];
            max_sum = max(max_sum, dp[i]);
        }
        return max_sum;
    }
};

在这里，仔细观察上面的代码，实际上只使用了dp[i-1]，可以将tmp_sum数组省去，直接用一个变量递推即可，因为只和前一次结果相关。
代码更改后如下：

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

执行结果如下：

执行时间与上面的类似。

参考：
https://segmentfault.com/a/1190000003481202