题目链接

[https://leetcode.cn/problems/maximum-subarray/description/](53. 最大子数组和 "https://leetcode.cn/problems/maximum-subarray/description/")

思路

分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律

表示状态

我们用 dp[i] 表示加到第 i 个数的累加和

找状态转移方程

边界处理

很容易知道 \(dp[0] = nums[0]\)，并且 \(result = nums[0]\)

空间优化

因为 \(dp[i]\) 只和 \(dp[i-1]\) 有关，所以可以不断更新维护单变量 sum 求出最终结果。

代码

`dp`数组版

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

        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(dp[i - 1] < 0){
                dp[i] = nums[i];
            }else{
                dp[i] = nums[i] + dp[i - 1];
            }

            result = Math.max(result, dp[i]);
        }

        return result;
    }
}

空间优化版

class Solution {
    public int maxSubArray(int[] nums) {
        int result = nums[0];
        int sum = nums[0];

        for(int i = 1; i < nums.length; i++){
            if(sum < 0){
                sum = nums[i];
            }else{
                sum = nums[i] + sum;
            }

            result = Math.max(result, sum);
        }

        return result;
    }
}