最大子序列和問題

問題： 

給定一整數序列a1， a2，... an （可能有負數），求a1~an的一個子序列ai~aj，使得ai到aj的和最大。 

例如：整數序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和為19。對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環，依次求出所有子序列的和然後取最大的那個。當然算法複雜度會達到o(n^3)。

這個算法很簡單，i表示子序列起始下标，j表示子序列結束下标，周遊子序列的開頭和結束下标，計算子序列的和，然後判斷最大子序列。很明顯的看出算法複雜度是o(n^3)。

顯然這種方法不是最優的，下面給出一個算法複雜度為o(n)的線性算法實作，算法的來源于programming pearls一書。在給出線性算法之前，先來看一個對窮舉算法進行優化的算法，它的算法複雜度為o(n^2)。其實這個算法隻是對對窮舉算法稍微做了一些修改：其實子序列的和我們并不需要每次都重新計算一遍。假設sum(i, j)是a[i] ... a[j]的和，那麼sum(i, j+1) = sum(i, j) + a[j+1]。利用這一個遞推，我們就可以得到下面這個算法：

那怎樣才能達到線性複雜度呢？這裡運用動态規劃的思想。先看一下源代碼實作：

在這一遍掃描數組當中，從左到右記錄目前子序列的和temp_sum，若這個和不斷增加，那麼最大子序列的和max也不斷增加(不斷更新max)。如果往前掃描中遇到負數，那麼目前子序列的和将會減小。此時temp_sum 将會小于max，當然max也就不更新。如果temp_sum降到0時，說明前面已經掃描的那一段就可以抛棄了，這時将temp_sum置為0。然後，temp_sum将從後面開始将這個子段進行分析，若有比目前max大的子段，繼續更新max。這樣一趟掃描結果也就出來了。 

分治法：

最大子序列和可能出現在三個地方：整個出現在輸入資料的左半部分，整個出現在輸入資料的右半部分，或者跨越輸入資料的中部進而占據左右兩個半部分。

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。

http://www.cnblogs.com/luxiaoxun/archive/2012/08/05/2623806.html