1. 概述
最大子数组问题（Maximum Subarray Problem）的目标是在给定数组中，找出一个连续的子数组，使其元素之和最大。
举个例子，在下面这个数组中，高亮部分的子数组拥有最大和（6）：
本文将介绍两种解决该问题的方案。其中一种我们会设计成时间复杂度和空间复杂度均为 O(n) 的高效解法。
✅ 提示：这个问题在面试中高频出现，掌握其动态规划解法（Kadane算法）是必备技能。
2. 暴力解法（Brute Force）
暴力解法是一种通过嵌套遍历穷举所有可能情况的策略。虽然直观，但效率较低，适合小规模数据验证逻辑。
2.1. 思路解析
最直接的想法是：枚举所有可能的连续子数组，计算它们的和，然后记录最大值。
具体做法是：
- 外层循环控制子数组的起始位置
left - 内层循环从
left开始向右扩展，逐步累加元素，形成以left起始的所有子数组 - 每次累加后更新全局最大和，并记录对应的起始与结束索引
如下图所示，左侧是从索引 0 开始的遍历过程，右侧是从索引 3 开始的遍历：
最终我们会遍历所有从 0 到 n-1 的起始位置，确保不遗漏任何子数组。
2.2. Java 实现
public int maxSubArray(int[] nums) {
int n = nums.length;
int maximumSubArraySum = Integer.MIN_VALUE;
int start = 0;
int end = 0;
for (int left = 0; left < n; left++) {
int runningWindowSum = 0;
for (int right = left; right < n; right++) {
runningWindowSum += nums[right];
if (runningWindowSum > maximumSubArraySum) {
maximumSubArraySum = runningWindowSum;
start = left;
end = right;
}
}
}
logger.info("Found Maximum Subarray between {} and {}", start, end);
return maximumSubArraySum;
}
⚠️ 注意：
maximumSubArraySum初始化为Integer.MIN_VALUE，避免数组全为负数时出错。
我们通过 start 和 end 记录最大子数组的边界，便于后续定位原始数据位置。
2.3. 复杂度分析
- ✅ 时间复杂度：O(n²)
两层嵌套循环，对每个起始位置都要遍历到末尾。 - ✅ 空间复杂度：O(1)
仅使用常量级额外变量。
虽然逻辑清晰，但当数组规模变大时，性能急剧下降。不推荐用于生产环境或大规模数据处理。
3. 动态规划解法（Kadane 算法）
动态规划的核心思想是：将原问题拆解为若干子问题，通过复用子问题的解来避免重复计算，即所谓的“记忆化（memoization）”。
3.1. Kadane 算法简介
Kadane 算法是解决最大子数组问题的经典动态规划方案，其关键在于定义合适的子问题状态转移方程。
✅ 核心挑战：如何定义“最优子结构”？
3.2. 思路推导
换个角度思考：假设我们知道以 i-1 结尾的最大子数组和，那么以 i 结尾的最大子数组和是多少？
看这张图：
我们定义：
maxEndingHere：表示以当前索引结尾的最大子数组和maxSoFar：记录遍历过程中的全局最大值
状态转移逻辑如下：
maxEndingHere = max(arr[i], maxEndingHere + arr[i])
这个公式的意思是：
- 要么抛弃之前的累加结果，从当前元素重新开始（因为之前累加拖后腿了）
- 要么继续扩展之前的子数组
举个例子，如果前面累加和是 -2，当前元素是 5，显然从 5 重新开始更划算。
我们只需一次遍历即可完成所有子问题求解：
图中高亮的是当前遍历到的元素。通过不断更新 maxEndingHere 和 maxSoFar，最终 maxSoFar 就是答案。
3.3. Java 实现
public int maxSubArraySum(int[] arr) {
int size = arr.length;
int start = 0;
int end = 0;
int maxSoFar = arr[0], maxEndingHere = arr[0];
for (int i = 1; i < size; i++) {
maxEndingHere = maxEndingHere + arr[i];
// 决定是否从当前元素重新开始
if (arr[i] > maxEndingHere) {
maxEndingHere = arr[i];
if (maxSoFar < maxEndingHere) {
start = i;
}
}
// 更新全局最大值
if (maxSoFar < maxEndingHere) {
maxSoFar = maxEndingHere;
end = i;
}
}
logger.info("Found Maximum Subarray between {} and {}", Math.min(start, end), end);
return maxSoFar;
}
⚠️ 为什么用
Math.min(start, end)？
当数组全为负数时，start可能会大于end（因为start在内层条件中更新更频繁），所以取最小值保证区间正确。
3.4. 复杂度分析
- ✅ 时间复杂度：O(n)
仅需一次遍历。 - ✅ 空间复杂度：O(1)
同样只用几个变量。
相比暴力解法，这是质的飞跃。线性时间意味着即使处理百万级数据也毫无压力。
4. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否推荐 |
|---|---|---|---|
| 暴力解法 | O(n²) | O(1) | ❌ 仅用于理解逻辑 |
| Kadane 算法 | O(n) | O(1) | ✅ 生产环境首选 |
- ✅ 暴力解法：简单粗暴，适合小数据验证
- ✅ Kadane 算法：动态规划经典案例，必须掌握
- ✅ 踩坑提醒：初始化值、全负数场景、索引边界处理
💡 拓展建议：可尝试用类似思路解决“最大子矩阵和”问题，本质是降维 + Kadane。
完整代码示例已托管至 GitHub：https://github.com/dev-tutorials/algorithms-max-subarray