30 核心算法 第07集：Kadane算法

Source: Dev.to

概述

许多系统之所以失败，并不是因为缺乏动力，而是因为它们拒绝放弃已有的动力。
Kadane 算法回答了一个看似简单却颇具挑战性的问题：何时继续的代价大于重新开始的代价？

它并不限于数组。想象一下随时间跟踪性能：有些区段贡献为正，有些为负。朴素的做法是独立评估每一个可能的区段，期望在数据的某处找到最佳结果。虽然这样可行，但并不是所有的历史都值得被记住。有时最好的决定是停止携带过去的负担。

核心思想

Kadane 算法遵循一条严格的规则：

如果过去伤害了现在，就把它丢掉。

在每一步，算法决定是继续扩展当前序列更有利，还是重新开始能得到更好的结果。这个决定是局部的，而不是全局比较。

算法

best = float('-inf')
current = 0

for value in sequence:
    current = max(value, current + value)
    best = max(best, current)

• current 保存以当前位结束的最大和。
• best 记录迄今为止看到的整体最大值。

算法不记忆子数组；每一步只问一个问题：“保留我已有的东西还能帮助吗？”

为什么有效

Kadane 的观察既简单又强大：

如果运行中的累计和变为负数，它只会降低随后所有值的总和。

因此，算法从不犹豫放弃负的前缀。这种随时重置的意愿使得解保持最优，而无需回溯过去的决定。

超出数组的应用

同样的逻辑出现在任何系统需要在噪声中检测有意义的连续段落时，例如：

• 性能连胜
• 金融盈亏周期
• 信号处理中的峰值

在这些场景中，目标不是保持连续性，而是找出最有利的连续区段。

局限性

Kadane 假设重新开始的代价很低。如果重置状态代价高昂，或历史信息具有长期依赖性，算法的逻辑可能失效。它在以下情况下表现不佳：

• 多维约束
• 延迟惩罚
• 恢复成本重要的系统

权衡

Kadane 决断果断，却不够谨慎。它用即时性换取了完整性：

• 优点： 线性时间 (O(n))、常数空间 (O(1))，并在其解决的问题上提供最优解。
• 缺点： 它不遍历所有可能的区段，只考虑能够逐步构建的那些。

收获

Kadane 算法不仅仅是寻找最大子数组，它更在于知道何时过去的努力不再是资产，并具备立即放手的纪律。这一原则在所有需要区分真实动能与累计阻力的系统中随处可见，这也是 Kadane 成为核心算法而非仅仅是巧妙技巧的原因。