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

难度: 🌕

问题描述

---

解法

class Solution {
    public int maxSubArray(int[] nums) {
        // 思路：
        // dp[i] = max(dp[i - 1] + [i], 0)
        int len = nums.length;
        if(len == 1) {
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = Math.max(nums[0], 0);
        int res = nums[0];

        for(int i = 1; i < len; i ++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

---

输出