剑指 Offer 42. 连续子数组的最大和

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < len; i++){
        //dp[i - 1] > 0  则 +nums[i]会更大
        //dp[i - 1] <= 0  则 +nums[i]会更小
        //此处 + nums[i]后情况判断dp[i]的最大值
        //若之前dp[i - 1] <= 0，则可以理解为更新子数组的起始位置为nums[i]
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        //每一轮筛选一次最大值，更新给res
            res = Math.max(dp[i], res);
        }
        return res;
    }
}