class Solution {
public:
    //动态规划
    int maxSubArray(vector<int>& nums) {
        int length=nums.size();
        vector<int> dp(length+1,0);
        int ans=nums[0];
        dp[0]=nums[0];
        int i=1;
        while(i<length){
            dp[i]=nums[i]+(dp[i-1]>0?dp[i-1]:0);
            ans=max(ans,dp[i]);
            i++;
        }
        for(int i=0;i<=length;i++){
            cout<<dp[i]<<" ";
        }
        return ans;
    }
};

4.优化：两个变量记录动规

class Solution {
public:
    //动态规划
    int maxSubArray(vector<int>& nums) {
        int pre=0,ans=nums[0];
        for(auto i:nums){
            pre=max(pre+i,i);
            ans=max(ans,pre);
            cout<<ans<<" ";
        }
        return ans;
    }
}