连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

思路：

数组nums,记 dp[i]，表示以下标i为结尾的子数组的和的最大值，则有dp[i]=max(dp[i-1]+nums[i],nums[i])，即dp[i-1]加上当前数和当前数比较，取其中较大值为dp[i]的值。答案为max(dp[0...n-1]),n为nums的长度。因为dp[i]只和dp[i-1]有关，所以，可以使用一个变量表示dp[i-1]，另一个变量表示d[i]。

代码：

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