1、前言

题目描述

2、思路

1⃣️ 思路很简单，只要和大于0，一直加即可，如果每一步的和比最大的还大，则记录下来。如果和小于0，则累加的操作重新开始。

2⃣️ 动态规划法：
定义 dp[i] 为数组以 nums[i] 结尾的连续子数组最大和。

if (dp[i - 1] < 0) {
    dp[i] = nums[i];        // 前面是负资产，丢掉，另起炉灶
} else {
    dp[i] = dp[i - 1] + nums[i]; // 前面是正资产，继承下来
}

简洁一点的写法，那么 dp[i] = max{ dp[i - 1] + nums[i], nums[i] }。
解释如下：假设数组都为正数（这样方便找状态转移方程），当 dp[i - 1] >= 0 的时候，当然加上更大；当 dp[i - 1] < 0 时，还不如不要。

3、代码

简单思路：

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0, max = Integer.MIN_VALUE;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            max = Math.max(max, sum);
            if(sum < 0){
                sum = 0;
            }
        }

        return max;
    }
}

动态规划：

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        // base case
        dp[0] = nums[0];
        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        }

        int max = Integer.MIN_VALUE;
        for(int i = 0; i < dp.length; i++){
            max = Math.max(dp[i], max);
        }

        return max;
    }
}