class Solution {
public:
    //这次遍历的对象是0~1 0~2....0~(n-1),但是加上一个条件：最右边的单个元素的一定要！
    //也就是说，这回的dp表示的是：包含最后一个元素的最大值。有可能不包含最后一个时的值更大，所以需要我们再加一步：和max比较大小
    //这道题这么绕一下，不向上一题一样，直接一个递推式子就完成了的原因是：在这道题中找不大合适的递推公式
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        std::vector<int> dp(nums.size()+1, 0);
        
        dp[0] = nums[0];
        dp[1] = nums[1]+nums[0] > nums[1] ? nums[1]+nums[0] : nums[1];
        
        int max = dp[0] > dp[1] ? dp[0]: dp[1];
        for(int i = 2; i < nums.size(); i++){
            // 这里的if-else就是递推式子
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + nums[i];
                
            }
            else{
                dp[i] = nums[i];
            }
            
            if(max < dp[i]) max = dp[i];
            // printf("%d- ",dp[i]);
        }
       
        return max;
    } 
};