动态规划中等3 种解法

#53最大子数组和

在非空整数数组中寻找和最大的连续子数组，并返回其元素和。

#数组#动态规划#贪心

解题主线

以位置 i 结尾的最大子数组和只取决于 nums[i] 与前一位置的最优值：若前缀贡献为负，就从当前位置重新开始。

Kadane 算法可以理解为动态规划的状态压缩，也可以从贪心角度理解为及时丢弃负贡献前缀。

全负数组不能把答案初始化为 0；必须用首元素或 Integer.MIN_VALUE 保留最大的负数。

解法 1：枚举起点与终点

固定每个起点，向右累加并更新最大值；复用当前区间和，避免再套一层求和循环。

时间复杂度

O(n²)

空间复杂度

O(1)

53. 最大子数组和 · 枚举起点与终点

java

final class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("nums must be non-empty");
        }

        int answer = Integer.MIN_VALUE;
        for (int left = 0; left < nums.length; left++) {
            int sum = 0;
            for (int right = left; right < nums.length; right++) {
                sum += nums[right];
                answer = Math.max(answer, sum);
            }
        }
        return answer;
    }
}

固定每个起点，向右累加并更新最大值；复用当前区间和，避免再套一层求和循环。

这是验证优化解法的直接基线；若每个区间重新求和，时间会退化到 O(n³)。

解法 2：动态规划

令 dp[i] 为必须以 nums[i] 结尾的最大子数组和，转移为 dp[i] = max(nums[i], dp[i - 1] + nums[i])。

时间复杂度

O(n)

空间复杂度

O(n)

53. 最大子数组和 · 动态规划

java

final class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("nums must be non-empty");
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int answer = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }
}

令 dp[i] 为必须以 nums[i] 结尾的最大子数组和，转移为 dp[i] = max(nums[i], dp[i - 1] + nums[i])。

解法 3：Kadane 贪心

维护当前连续段的和；一旦它变成负数，它只会拖累后续区间，因此在记录答案后将其丢弃并从下一项重新累计。

时间复杂度

O(n)

空间复杂度

O(1)

53. 最大子数组和 · Kadane 贪心

java

final class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("nums must be non-empty");
        }

        int answer = Integer.MIN_VALUE;
        int currentSum = 0;
        for (int value : nums) {
            currentSum += value;
            answer = Math.max(answer, currentSum);
            if (currentSum < 0) {
                currentSum = 0;
            }
        }
        return answer;
    }
}

维护当前连续段的和；一旦它变成负数，它只会拖累后续区间，因此在记录答案后将其丢弃并从下一项重新累计。

该写法与一维 DP 使用同一最优子结构，但省去了 dp 数组。

边界与易错点

题目要求子数组非空，不能用空子数组把全负输入的答案错误地变成 0。
连续子数组不同于子序列，不能跳过中间元素。
两份旧源码中的 Kadane 和数组 DP 实现重复；整理后各保留一种，并补充一份 O(n²) 枚举作为复杂度基线。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q053_maxSubArray.javaleetcode/src/main/java/greedy/Q053_maxSubArray1.java