1、摘要本文分析并演示最大子序列和問題的幾種算法，它們都能解決問題，但是時間復(fù)雜度卻大相徑庭，最后將逐步降低至線性。算法子序列和問題的引入給定（可能有負(fù)數(shù)）整數(shù)序列A1A2A3...An，求這個序列中子序列和的最大值。（為方便起見，如果所有整數(shù)均為負(fù)數(shù)，則最大子序列和為0）。例如：輸入整數(shù)序列：2118411650，則輸出答案為35，即從A2～A6。這個問題之所以有吸引力，主要是因為存在求解它的很多算法，而這些算法的性能差異又很大。這些算法

2、，對于少量的輸入差別都不大，幾個算法都能在瞬間完成，這時若花費大量的努力去設(shè)計聰明的算法恐怕就不太值得了；但是如果對于大量的輸入，想要更快的獲取處理結(jié)果，那么設(shè)計精良的算法顯得很有必要。切入正題下面先提供一個設(shè)計最不耗時間的算法，此算法很容易設(shè)計，也很容易理解，但對于大量的輸入而言，效率太低：算法一：publicstaticintmaxSubsequenceSum(int[]a)intmaxSum=0f(inti=0ia.lengthi

3、)i為子序列的左邊界f(intj=ija.lengthj)j為子序列的右邊界intthisSum=0f(intk=0k=jk)迭代子序列中的每一個元素，求和maxSum=thisSumreturnmaxSum對于此算法，時間復(fù)雜度顯然是O(N2)，對它的分析甚至比前面的分析還要簡單，就是直接使用窮舉法把序列中i后面的每個值相加，如果發(fā)現(xiàn)有比maxSum大的，則更新maxSum的值。對于這個問題，有一個遞歸和相對復(fù)雜的O(NlogN)解法

4、，我們現(xiàn)在就來描述它。要是真的沒有出現(xiàn)O(N)（線性的）解法，這個算法就會是體現(xiàn)遞歸為例的極好的范例了。該方法采用一種“分治”策略。其想法就是吧問題分成兩個大致相等的子問題，然后遞歸地對它們求解，這是“分”的階段?！爸巍彪A段就是將兩個子問題的解修補(bǔ)到一起并可能再做些少量的附加工作，最后得到整個問題的解。在我們的例子中，最大子序列的和只可能出現(xiàn)在3個地方：1.出現(xiàn)在輸入數(shù)據(jù)的左半部分2.3.出現(xiàn)在輸入數(shù)據(jù)的右半部分4.5.跨越輸入數(shù)據(jù)的中