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]

• 最终结果：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]); // 输出: 6
        System.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 算法是一种高效的动态规划算法，核心在于维护以当前元素为结尾的最大子数组和，更新全局最大值。它可以轻松扩展以处理不同的变体问题，例如返回子数组本身、处理二维矩阵等，因其高效性和简单性而广泛应用。