sko.kr

算法 - 0. Kadane算法

algorithmsdynamic-programmingarraysoptimizationkadane
By sko•9/27/2025•6 min read

何时使用 Kadane 算法

当你需要基于某种累积属性找到最优连续子数组时，使用 Kadane 算法。虽然最常用于最大和，但可以适应于：

  • 最大和（经典用例）
  • 最大乘积（需要修改以处理负数/零）
  • 具有特定属性的最长子数组（例如：和等于 k）
  • 最小和（通过取反值或反转比较）
  • 任何可以基于累积状态做出扩展或重启的局部决策的问题

示例问题

股票交易：给定每日股价变化 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，找出持有股票的最佳连续期间。

  • 第 0 天：损失$2
  • 第 1 天：收益$1
  • 第 2 天：损失$3
  • ...依此类推

答案：从第 3 天持有到第 6 天（子数组 [4, -1, 2, 1]）获得总计$6 的收益。

最重要的洞察

每个子数组都必须在某处结束 - 在每个位置，我们做出最优的局部决策（扩展 vs 重新开始），通过检查所有可能的终点及其最优起点来保证找到全局最大值。

思维笔记：这个算法的精髓在于聚焦"在索引 i 处结束的最佳子数组"。在每个位置，我们只需要决定："应该将当前元素添加到在前一个索引结束的最佳子数组中，还是重新开始？"这个简单的决定自动探索了所有可能的子数组。

决策框架

在每个元素处，你面临一个简单的决策：

  • 扩展当前子数组（添加到已有的）
  • 用新的子数组重新开始（放弃过去）

代码

function kadanes(nums: number[]) {
  let globalMax = nums[0];
  let localMax = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const currentNum = nums[i];
    // 决策框架
    const extendSubarray = localMax + currentNum;
    const startNewSubarray = currentNum;
    localMax = Math.max(startNewSubarray, extendSubarray);

    globalMax = Math.max(globalMax, localMax);
  }

  return globalMax;
}

疑虑破解

常见疑虑："算法只在每个位置考虑扩展或重新开始。如果删除当前子数组的前几个元素会得到更大的和呢？"

这是关于 Kadane 算法的一个精妙的担忧。让我们用具体例子来解决它。

为什么你可能认为它会错过更好的子数组

考虑数组 [-2, 3, 5, -1, 6]。在跟踪子数组时，你可能会想：

  • "在位置 4，子数组 [3, 5, -1, 6] 的和是 13"
  • "但如果我们有像 [-2, 3, 5, -1, 6] 这样的子数组，只想删除-2 怎么办？"
  • "算法似乎只能在末尾添加或完全重新开始 - 不能从开头删除吗？"

为什么这种想法是错误的

关键认识：所有可能的"部分删除"都已经在之前的位置被考虑过了！

让我们跟踪 [-2, 3, 5, -1, 6] 来看看 Kadane 如何处理这个：

位置 0: localMax = -2  ([-2])
位置 1: localMax = 3   ([3])         → 比较: -2+3=1 vs 3，选择3（删除了-2！）
位置 2: localMax = 8   ([3, 5])      → 比较: 3+5=8 vs 5，选择8
位置 3: localMax = 7   ([3, 5, -1])  → 比较: 8+(-1)=7 vs -1，选择7
位置 4: localMax = 13  ([3, 5, -1, 6]) → 比较: 7+6=13 vs 6，选择13

神奇时刻：在位置 1，当我们选择用 3 重新开始而不是扩展得到 1 时，我们自动删除了-2！算法已经考虑并做出了最优选择。

具体例子：所有删除可能性都被涵盖

想想你可能想要的任何子数组 - 比如说你担心错过 [5, -1, 6]（删除-2 和 3）：

  • 删除第一个元素[-2]：在位置 1 重新开始时已经考虑
  • 删除前两个元素[-2, 3]：在位置 2 比较重新开始(5) vs 扩展(8)时已经考虑
  • 删除前三个元素[-2, 3, 5]：在位置 3 比较重新开始(-1) vs 扩展(7)时已经考虑

在位置 4 结束的子数组的每个可能起点都已经在我们计算每个之前位置结束的最佳子数组时被评估过了！

为什么局部决策保证检查所有情况

Kadane 算法的精妙之处在于"重新开始"不仅仅意味着重新开始 - 它意味着：

  • "这个点之前的所有内容都会让我的和变差"
  • "包含之前元素的所有可能子数组都已经被评估过"
  • "通过删除所有内容，我正在做出最优选择"

当我们扩展时，我们在说"从最优起点保留所有内容仍然是有益的"。当我们重新开始时，我们在说"删除所有内容 - 即使是在这个点之前结束的最佳子数组也会让情况变差"。

保证：因为每个子数组都必须在某处结束，而我们为每个可能的结束位置找到最优起点，所以我们隐式地检查了每个可能的子数组 - 包括所有从开头删除各种元素的子数组！

← Back to Blog