Kadane 算法

定义

Kadane 算法用于求解最大子数组和问题:在一个含正负数的数组中找出和最大的连续子数组。该算法由统计学家 Jay Kadane 于 1984 年前后给出,时间复杂度 O(n)、空间 O(1)。

原理

本质是简化的动态规划:设 cur 为以当前元素结尾的最大子数组和,转移为 cur = max(nums[i], cur + nums[i]),即若之前的累积为负则果断另起炉灶;全程维护 cur 的历史最大值即为答案。记录转移决策点即可还原具体子数组区间。

背景

最大子数组问题最初由 Ulf Grenander 在图像模式识别研究中提出,经 Jon Bentley 在《Programming Pearls》专栏中讨论从 O(n³)、O(n²)、分治 O(n log n) 到线性解的演进而广为人知,成为算法设计层层优化的教学范例。

应用与变体

股票单笔买卖最大收益、信号片段检测等;环形数组版本、二维矩阵最大子矩阵和均可在其基础上扩展。