动态规划中等3 种解法
#53最大子数组和
在非空整数数组中寻找和最大的连续子数组，并返回其元素和。
#数组#动态规划#贪心
原题
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解题主线
- 以位置 i 结尾的最大子数组和只取决于 nums[i] 与前一位置的最优值：若前缀贡献为负，就从当前位置重新开始。
- Kadane 算法可以理解为动态规划的状态压缩，也可以从贪心角度理解为及时丢弃负贡献前缀。
- 全负数组不能把答案初始化为 0；必须用首元素或 Integer.MIN_VALUE 保留最大的负数。
解法 1：枚举起点与终点
固定每个起点，向右累加并更新最大值；复用当前区间和，避免再套一层求和循环。
-
时间复杂度： O(n²)
-
空间复杂度： O(1)
final class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("nums must be non-empty");
}
// 子数组必须非空，避免全负数组错误地选择和为 0 的空区间。
// 后续循环只扩展连续区间，并同步维护当前候选与全局最优。
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)
final class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("nums must be non-empty");
}
// 子数组必须非空，避免全负数组错误地选择和为 0 的空区间。
// 后续循环只扩展连续区间，并同步维护当前候选与全局最优。
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;
}
}解法 3：Kadane 贪心
维护当前连续段的和；一旦它变成负数，它只会拖累后续区间，因此在记录答案后将其丢弃并从下一项重新累计。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("nums must be non-empty");
}
// 子数组必须非空，避免全负数组错误地选择和为 0 的空区间。
// 后续循环只扩展连续区间，并同步维护当前候选与全局最优。
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