Kadane算法扫描一次整个数列的所有数值，在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。该子数列由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出），该算法可看成动态规划的一个例子。

• 给定一个数列，例如【−2, 1, −3, 4, −1, 2, 1, −5, 4】， 求一个连续的数列使得数列内的元素和最大， 示例中最大子数列应该是【4, −1, 2, 1】, 求和值为6。

• 这个问题是可以衍生到一些变种问题， 如寻找数列中最大乘积序列，且要求序列中，相邻元素间隔不超过限定值等， 常出现在笔试面试编程题中。

• 该问题最早于1977年提出，但是直到1984年才被Jay Kadane 发现了线性时间的最优解法，所以算法虽然长度很短，但其实并不容易理解。

• 算法描述：

• 遍历该数组， 在遍历过程中， 将遍历到的元素依次累加起来， 当累加结果小于或等于0时， 从下一个元素开始，重新开始累加。

• 累加过程中， 要用一个变量(max_so_far)记录所获得过的最大值

• 一次遍历之后， 变量 max_so_far 中存储的即为最大子片段的和值。

• 此处为python 代码 ， 变量A 传入数组。

• 首先， 题目中有一个隐含的设定， 最大子片段是可以为空的， 空片段的和值是0。 这一点必须要明确， 不然会无法理解算法的正确性， 所以当给定的数列中，求和为负数的时候，例如【-2，1， -3】， 算法会返回最大求和值0， 因为默认该数组的最大子片段是一个空序列。

• 理解此算法的关键在于:

算法可用如下Python代码实现：

defmax_subarray(A):max_ending_here=max_so_far=A[0]forxinA[1:]:max_ending_here=max(x,max_ending_here x)max_so_far=max(max_so_far,max_ending_here)returnmax_so_far

该问题的一个变种是：如果数列中含有负数元素，允许返回长度为零的子数列。该问题可用如下代码解决：

defmax_subarray(A):max_ending_here=max_so_far=0forxinA:max_ending_here=max(0,max_ending_here x)max_so_far=max(max_so_far,max_ending_here)returnmax_so_far

这种算法稍作修改就可以记录最大子数列的起始位置。Kadane算法时间复杂度为O(n)，空间复杂度为O(1)。