Kadane 算法 详解

Kadane 算法详解

Kadane 算法是一种动态规划思想的算法，用于解决 “最大子数组和”（Maximum Subarray Sum） 问题。该算法以其简单且高效的特点广泛应用于面试和实践中。

---

问题描述

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

例如：

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 最大子数组为 [4,-1,2,1]，其和为 6。

---

Kadane 算法核心思想

1. 定义状态变量：

   • currentSum：表示以当前元素为结束的子数组的最大和。
   • maxSum：记录全局最大子数组和。

2. 动态规划转移方程：
   对于数组中的每个元素 nums[i]：

   • 如果 currentSum + nums[i] > nums[i]，则将当前元素加到之前的子数组中（即扩展子数组）。
   • 如果 currentSum + nums[i] <= nums[i]，则重新开始一个新的子数组，从 nums[i] 开始。
   • 转移方程：
     $$currentSum=\max (currentSum+nums[i],nums[i])$$

3. 更新全局最大值：

   • 在每一步计算中，比较 currentSum 和 maxSum，更新全局最大值：
     $$maxSum=\max (maxSum,currentSum)$$

4. 时间复杂度：

   • 遍历一次数组，时间复杂度为 $O(n)$。
   • 空间复杂度为 $O(1)$，只需常量空间记录 currentSum 和 maxSum。

---

Kadane 算法的实现

代码实现

public class Kadane {public static int maxSubArray(int[] nums) {// 初始化变量int currentSum = nums[0]; // 以第一个元素开始int maxSum = nums[0];     // 全局最大值for (int i = 1; i < nums.length; i++) {// 动态规划转移方程currentSum = Math.max(currentSum + nums[i], nums[i]);// 更新全局最大值maxSum = Math.max(maxSum, currentSum);}return maxSum;}public static void main(String[] args) {int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println("最大子数组和为: " + maxSubArray(nums)); // 输出: 6}
}

---

Kadane 算法的步骤分析

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

索引 i	nums[i]	currentSum	maxSum
0	-2	-2	-2
1	1	$\max (-2+1,1)=1$	1
2	-3	$\max (1-3,-3)=-2$	1
3	4	$\max (-2+4,4)=4$	4
4	-1	$\max (4-1,-1)=3$	4
5	2	$\max (3+2,2)=5$	5
6	1	$\max (5+1,1)=6$	6
7	-5	$\max (6-5,-5)=1$	6
8	4	$\max (1+4,4)=5$	6

• 最终结果：maxSum = 6，对应子数组 [4, -1, 2, 1]。

---

扩展问题

1. 返回最大子数组本身

Kadane 算法的简单实现只返回最大和，如果需要返回子数组本身，可以增加两个变量记录子数组的起始和结束索引。

public class KadaneWithSubarray {public static int[] maxSubArray(int[] nums) {int currentSum = nums[0], maxSum = nums[0];int start = 0, end = 0, tempStart = 0;for (int i = 1; i < nums.length; i++) {if (currentSum + nums[i] > nums[i]) {currentSum += nums[i];} else {currentSum = nums[i];tempStart = i; // 更新临时起始索引}if (currentSum > maxSum) {maxSum = currentSum;start = tempStart; // 更新起始索引end = i;           // 更新结束索引}}// 返回子数组和最大和return new int[]{maxSum, start, end};}public static void main(String[] args) {int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int[] result = maxSubArray(nums);System.out.println("最大子数组和: " + result[0]); // 输出: 6System.out.println("最大子数组: " + Arrays.toString(Arrays.copyOfRange(nums, result[1], result[2] + 1))); // 输出: [4, -1, 2, 1]}
}

---

2. 处理全负数组

Kadane 算法可以直接处理全负数组，因为它初始化 currentSum 和 maxSum 为第一个元素，确保算法能够返回正确的结果（即最大负数）。

例如：nums = [-3, -5, -2, -8]。

• 输出：-2（子数组为 [-2]）。

---

3. 二维最大子矩阵问题

Kadane 算法可扩展到二维数组，用于求解矩阵中的最大子矩阵和问题。

大致思路：

1. 固定两个行边界。
2. 对每列求和，转换为一维数组问题。
3. 使用 Kadane 算法求解该一维数组的最大和。

---

时间复杂度与优化

• 时间复杂度：$O(n)$，每个元素遍历一次。
• 空间复杂度：$O(1)$，只使用了常量空间。

---

总结

Kadane 算法是一种高效的动态规划算法，核心在于维护以当前元素为结尾的最大子数组和，更新全局最大值。它可以轻松扩展以处理不同的变体问题，例如返回子数组本身、处理二维矩阵等，因其高效性和简单性而广泛应用。