一、题目内容

二、题解

解法1：

思路

动态规划，转移方程为

• dp[i-1] > 0
  • dp[i] = dp[i-1] + nums[i]
• dp[i-1]<0
  • dp[i] = nums[i]

动态规划四步：

• 状态：res结果表（取max，可以通过变量交换减少空间占用）
• 状态转移：值不值得加
• 初始状态：列表第一个数
• 结果：res最终值

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i-1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}