最大子数列之和

问题： 给定一个数列，例如【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 中存储的即为最大子片段的和值。

理解此算法的关键在于:

最大子片段中不可能包含求和值为负的前缀。 例如 【-2， 1，4】 必然不能是最大子数列， 因为去掉值为负的前缀后【-2，1】， 可以得到一个更大的子数列 【4】、

所以在遍历过程中，每当累加结果成为一个非正值时， 就应当将下一个元素作为潜在最大子数列的起始元素， 重新开始累加。

由于在累加过程中， 出现过的最大值都会被记录， 且每一个可能成为 最大子数列起始元素 的位置， 都会导致新一轮的累加， 这样就保证了答案搜索过程的完备性和正确性。

本文转自 zhegaozhouji 51CTO博客，原文链接:http://blog.51cto.com/1038741/1951646