注：
此动态规划题目可以将空间复杂度优化到O(1)。

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

要求时间复杂度为O(n)。

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

提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

题解：
动态规划解析
状态定义： 设动态规划列表 dp ，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。

转移方程： 若 dp[i−1]≤0 ，说明dp[i−1] 对 dp[i] 产生负贡献，即 dp[i-1] + nums[i] 还不如 nums[i] 本身大。
当 dp[i - 1] > 0时：执行 dp[i] = dp[i-1] + nums[i]；
当 dp[i−1]≤0 时：执行 dp[i] = nums[i] ；

初始状态： dp[0] = nums[0]，即以 nums[0] 结尾的连续子数组最大和为 nums[0]。

返回值： 返回 dp 列表中的最大值，代表全局最大值。

空间复杂度降低
1、修改原数组
由于 dp[i] 只与 dp[i−1] 和nums[i] 有关系，因此可以将原数组 nums用作 dp 列表，即直接在 nums 上修改即可。
由于省去 dp 列表使用的额外空间，因此空间复杂度从 O(N) 降至 O(1) 。
2、不修改原数组
有的时候，题目要求可能不能修改原有数组，考虑到在dp列表中，dp[i]只和dp[i-1]有关,所以用两个参数存储循环过程中的dp[i]和dp[i-1]的值即可，空间复杂度也为O(1)。

复杂度分析：
时间复杂度 O(N) ： 线性遍历数组 nums 即可获得结果，使用 O(N)O(N) 时间。
空间复杂度 O(1) ： 使用常数大小的额外空间。

//空间复杂度优化前
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0]=nums[0];
        int maxsum=dp[0];
        for(int i=1;i<nums.size();++i){
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
            maxsum=max(dp[i],maxsum);
        }
        return maxsum;
    }
};
//空间复杂度优化后
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre=0;//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0
        int cur=nums[0];//用于记录dp[i]的值
        int maxsum=cur;
        for(int i=0;i<nums.size();++i){
            if(pre>0){
                cur=pre+nums[i];
            }
            else{
                cur=nums[i];
            }
            if(cur>maxsum){
                maxsum=cur;
            }
            pre=cur;
        }
        return maxsum;
    }
};