最大子数组和问题-详解Kadane算法

最大子数组和（Maximum Subarray Sum）是一个经典且高频的数组算法考点，这个问题看似简单——从一个整数数组中找到和最大的连续子数组，但暴力求解的效率极低。Kadane算法（卡丹算法）作为专门解决此问题的高效方法，能在$O(n)$时间内完成求解，是动态规划思想的典型应用。本文我将深入解析Kadane算法的核心原理、实现细节、变种拓展及实际应用，结合Java代码示例，帮你彻底掌握这一高效算法。

一、问题定义与暴力解法

1.1 问题描述

给定一个整数数组nums（可能包含负数），找到一个连续子数组（至少包含一个元素），使得该子数组的和最大，返回这个最大和。

例如：

• 输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• 输出：6（对应子数组[4, -1, 2, 1]）

1.2 暴力解法的低效性

最直观的思路是枚举所有可能的子数组，计算其和并记录最大值：

// 暴力解法：枚举所有子数组
public int maxSubArrayBruteForce(int[] nums) {int maxSum = Integer.MIN_VALUE;int n = nums.length;for (int i = 0; i < n; i++) {  // 子数组起点int currentSum = 0;for (int j = i; j < n; j++) {  // 子数组终点currentSum += nums[j];maxSum = Math.max(maxSum, currentSum);}}return maxSum;
}

• 时间复杂度：$O(n^2)$（嵌套循环枚举所有子数组）。
• 局限性：当n超过$10^4$时，会因超时无法通过测试，必须寻找更高效的算法。

二、Kadane算法的核心原理

2.1 动态规划思想的应用

Kadane算法的本质是动态规划，其核心是用局部最优推导全局最优：

• 定义dp[i]为“以nums[i]为结尾的最大子数组和”。
• 对于每个元素nums[i]，有两种选择：
  1. 将nums[i]加入之前的子数组（即dp[i-1] + nums[i]）。
  2. 以nums[i]为起点重新开始一个子数组（即nums[i]）。
• 因此，状态转移方程为：
  dp[i] = max(nums[i], dp[i-1] + nums[i])
• 全局最大和即为所有dp[i]中的最大值。

2.2 优化空间复杂度

由于dp[i]仅依赖于dp[i-1]，无需存储整个dp数组，可改用一个变量currentMax记录当前值，将空间复杂度从$O(n)$优化至$O(1)$：

1. 初始化currentMax = nums[0]（以第一个元素为结尾的子数组和），maxSum = nums[0]（全局最大值）。
2. 从第二个元素开始遍历：
   • currentMax = max(nums[i], currentMax + nums[i])（更新局部最优）。
   • maxSum = max(maxSum, currentMax)（更新全局最优）。
3. 遍历结束后，maxSum即为结果。

三、Kadane算法的Java实现

3.1 基础版本（处理所有情况）

public class KadaneAlgorithm {public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) {return 0;  // 边界处理：空数组}int currentMax = nums[0];  // 以当前元素为结尾的最大子数组和int maxSum = nums[0];      // 全局最大子数组和for (int i = 1; i < nums.length; i++) {// 选择：加入之前的子数组 或 重新开始currentMax = Math.max(nums[i], currentMax + nums[i]);// 更新全局最大值maxSum = Math.max(maxSum, currentMax);}return maxSum;}public static void main(String[] args) {KadaneAlgorithm solution = new KadaneAlgorithm();int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(solution.maxSubArray(nums));  // 输出 6}
}

3.2 算法正确性验证

以示例nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]为例，分步验证：

索引i	nums[i]	currentMax（局部最优）	maxSum（全局最优）
0	-2	-2	-2
1	1	max(1, -2+1)=1	max(-2, 1)=1
2	-3	max(-3, 1-3)=-2	max(1, -2)=1
3	4	max(4, -2+4)=4	max(1, 4)=4
4	-1	max(-1, 4-1)=3	max(4, 3)=4
5	2	max(2, 3+2)=5	max(4, 5)=5
6	1	max(1, 5+1)=6	max(5, 6)=6
7	-5	max(-5, 6-5)=1	max(6, 1)=6
8	4	max(4, 1+4)=5	max(6, 5)=6

最终maxSum=6，与预期结果一致，验证了算法的正确性。

四、Kadane算法的变种与拓展

4.1 变种1：输出最大子数组的起止索引

除了最大和，有时需要返回子数组的具体位置（起点和终点索引）。只需在更新currentMax和maxSum时，同步记录索引：

public int[] maxSubArrayWithIndex(int[] nums) {if (nums == null || nums.length == 0) {return new int[]{-1, -1};  // 空数组返回无效索引}int currentMax = nums[0];int maxSum = nums[0];int start = 0, end = 0;  // 当前子数组起止索引int tempStart = 0;       // 临时起点（用于重新开始子数组时更新）for (int i = 1; i < nums.length; i++) {if (nums[i] > currentMax + nums[i]) {// 重新开始子数组，更新临时起点currentMax = nums[i];tempStart = i;} else {// 加入之前的子数组currentMax += nums[i];}// 更新全局最大和及起止索引if (currentMax > maxSum) {maxSum = currentMax;start = tempStart;end = i;}}return new int[]{start, end, maxSum};  // 起点、终点、最大和
}

4.2 变种2：限制子数组长度（最多k个元素）

问题：找到长度不超过k的连续子数组的最大和。
思路：结合Kadane算法和前缀和优化，用滑动窗口维护前缀和的最小值（需额外处理长度限制）：

public int maxSubArrayWithLimit(int[] nums, int k) {int n = nums.length;int[] prefixSum = new int[n + 1];  // 前缀和：prefixSum[i] = sum(nums[0..i-1])for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}int maxSum = Integer.MIN_VALUE;// 用单调队列维护前缀和的最小值（窗口内）Deque<Integer> deque = new ArrayDeque<>();deque.offer(0);  // 初始前缀和prefixSum[0] = 0for (int i = 1; i <= n; i++) {// 移除窗口外的前缀和（超过k个元素）while (!deque.isEmpty() && i - deque.peekFirst() > k) {deque.pollFirst();}// 当前前缀和 - 窗口内最小前缀和 = 最大子数组和maxSum = Math.max(maxSum, prefixSum[i] - prefixSum[deque.peekFirst()]);// 维护单调队列（保证前缀和递增）while (!deque.isEmpty() && prefixSum[i] <= prefixSum[deque.peekLast()]) {deque.pollLast();}deque.offer(i);}return maxSum;
}

4.3 变种3：允许子数组为空（返回0）

若题目允许子数组为空（即最大和可以是0，如所有元素为负数时），只需在最后对结果取max(0, maxSum)：

public int maxSubArrayAllowEmpty(int[] nums) {int currentMax = 0;  // 初始化为0（允许空数组）int maxSum = 0;for (int num : nums) {currentMax = Math.max(0, currentMax + num);  // 空数组对应0maxSum = Math.max(maxSum, currentMax);}return maxSum;
}

五、时间与空间复杂度

• 时间复杂度：$O(n)$，仅需遍历数组一次，每次操作均为常数时间。
• 空间复杂度：$O(1)$，仅使用固定数量的变量（基础版本），适合大规模数据。

六、实际应用场景

1. 股票收益分析：计算某段时间内连续持有股票的最大收益（将股价数组转为每日涨跌数组）。
2. 信号处理：在噪声信号中提取连续有效信号段（信号强度和最大的区间）。
3. 能源消耗优化：找到连续时间段内能源消耗最高的区间，用于负载均衡。
4. LeetCode经典题：LeetCode 53（最大子数组和）、LeetCode 152（乘积最大子数组，Kadane算法的变种）。

总结
Kadane算法通过动态规划思想，以$O(n)$时间和$O(1)$空间高效解决最大子数组和问题，是算法优化的典型案例。其核心在于“局部最优选择”——每个元素要么加入之前的子数组，要么重新开始，通过不断更新局部最优和全局最优得到结果。
在实际应用中需注意：

• 基础版本可直接解决无长度限制的最大子数组和问题。
• 变种问题（如限制长度、返回索引）可通过扩展算法逻辑实现。
• 结合前缀和、单调队列等工具，可处理更复杂的场景。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～