絕妙的算法——最大子序列和問(wèn)題

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

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

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

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