最大子數列之和

問題： 給定一個數列，例如【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