算法導(dǎo)論：最大子序列和
問題描述：
什么是最大子序列和呢?
就是給定一組序列，所有子序列中和最大的那一組序列。
比如這里給出一組序列{-2，11，-4，13}
這里列出了10個子序列。
其中20就是我們要求的最大子序列和。
關(guān)于最大子序列和有幾個注意事項：
1. 空序列也是子序列，它的和為0；
2. 如果序列中所有整數(shù)均為負(fù)數(shù)，則最大子序列和為0;
3.子序列一定是連續(xù)的;
窮舉法1
算法思想：窮舉所有子序列，找最大的。
如上圖所示，列出所有子序列，再找出其中最大的和，不過這其中會出現(xiàn)大量重復(fù)的計算，比如-2+11就計算了三遍，耗費大量時間，下面計算時間復(fù)雜度。
假如是有n個數(shù)的序列，那它會有多少個子序列呢？從1開始的子序列有n個，從2開始的子序列有n-1個，所以總共的子序列為：
現(xiàn)在我們知道了總序列數(shù)，也就是序列的個數(shù)，那這些序列和的計算次數(shù)是多少？
由1開始的子序列有n個，從{1，2}一直到{1，2····n-1,n}，我們在計算這些序列和時，{1，2}相當(dāng)于計算了1次，就是1+2。計算{1,2,3}時我們又計算了一次1+2，所以這次計算了2次，那由1開始的序列計算的次數(shù)就是1+2+····+n也就是圖中所示的結(jié)果。2開始的序列的計算次數(shù)就是1+2···+n-1，以此類推求出所有序列的計算次數(shù)，最后得出總的計算次數(shù)。所以時間復(fù)雜度為O(n3)
窮舉法2
算法思想：在某點開始的所有序列中找最大的，找最大的。
比如這里給出一組序列{-2，11，-4，13}，首先計算由-2開始的所有子序列和，再找出其中最大的
可以看到這種方法避免了窮舉法1中每次都要從頭開始相加而造成的大量浪費，下面我們依次計算由11，-4，13開始的序列，找出最大子序列和。
在分別求出以-2，11，-4，13開始的最大子序列和后，再選擇其中最大的那個，就是我們要找的最大子序列和。但是這其中依然包含了重復(fù)計算，如上圖所示，計算由-2開始的序列時，我們計算了11+-4+13，在計算由11開始的序列時，也依然計算了11+-4+13，造成了重復(fù)計算。
那所有這些序列的總共計算次數(shù)是多少呢？
在窮舉法2中，由1開始的序列有n個，但因為避免了窮舉法1中的重復(fù)計算，所以計算次數(shù)只有n次，總共的計算次數(shù)就是1+2+···+n次，所以時間復(fù)雜度是O(n2)。
分治法
分治法的設(shè)計思想：將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。
給出一個序列{a,b,c,d,e,f,g}，顯然最大子序列和只可能出現(xiàn)在三個地方：
1、輸入序列的左半部分；
2、輸入序列的右半部分；
3、跨越輸入序列的中部而位于左右兩個部分；
所以我們只需要分別找出這三個部分的最大子序列和，再比較這三個和的大小，找出最大的子序列和即可。
我們可以通過遞歸的方法找到左半部分最大子序列和lsum以及右半部分最大子序列和rsum。
找到跨越中部的最大子序列和，因為這個子序列和一定是跨越中部的，所以只需要確定好中部，然后使lmax以及rmax都為最大，那么csum就是我們要找的子序列。最后比較這三個子序列的大小，最大的和就是最大子序列和。這里使用的是分治法，分治法的時間復(fù)雜度為O(nlgn)，詳解請看分治法
動態(tài)規(guī)劃法
分析：
1、因為最大子序列和的最小取值為0，所以最大子序列的第一個元素不會是負(fù)的。
若a[i]<0,則a[i]開頭的序列，一定不如a[i+1]開頭的序列大。
2、同理任何負(fù)的子序列，不可能作為最大子序列和的前綴。
這里的{4、-5}不能作為子序列的前綴。
3、如若一個子序列和thisSum>0（其中thisSum是從第m項到第n項的和），那么最大子序列和一定不會以a[m+1]和a[n]之間的項開始。
這里{1、5、-3、2}這個序列和大于0，那么最大子序列和就不會是從5或者-3或者2開始的，因為由這些開始，加上前面的1會更大。
下面將用介紹具體的例子：
首先給出序列{-5、15、-2、13、-9、-1、9、-30、10、3}。
用標(biāo)記分別標(biāo)出，子序列和的起始位置，最大子序列和起使以及終點位置，此時三個位置都在-5這里。并且記錄下該時刻最大子序列和的值以及子序列和的值。
當(dāng)指針移動到15時，根據(jù)上面的第一條規(guī)則，最大子序列的第一個元素不為負(fù)數(shù)，所以此時三個標(biāo)記都要移動到15，子序列的和為15，同時更新最大子序列的和15。
當(dāng)指針移動到-2時，更新此時的子序列和為13，發(fā)現(xiàn)13<15,所以最大子序列和依然是15，且起使、終點位置也不改變。
當(dāng)指針移動到13時，子序列和變?yōu)?6>15，所以更新最大子序列和為26。并且最大子序列的終點位置也要發(fā)生變化。
在指針移動過-9、-1、9、-30時子序列和的值都沒有26打，所以最大子序列和并未更新，不過指針移動到-30時子序列和變?yōu)榱?5，也就是{15、-2、13、-9、-1、9、-30}和為-5，根據(jù)規(guī)則2，這個序列一定不會是最大子序列的前綴。而且{15、-2、13、-9、-1、9}這個序列的和是大于0的，根據(jù)規(guī)則3，最大子序列和一定不會是從{-2、13、-9、-1、9}這里面的某一項開始的。所以最大子序列和不會是以{15、-2、13、-9、-1、9、-30}為前綴開始的，也不會是以{15、-2、13、-9、-1、9、-30}中的某一項開始的。那么當(dāng)我們下一步，移動子序列起使位置的標(biāo)記時，就可以跳過這里面所有的數(shù)，移動到-30后面的數(shù)。
子序列和的起使位置變?yōu)榱?0，10<26，所以最大子序列和的值以及標(biāo)記依然不發(fā)生變化。
序列遍歷完成后，可從記錄中得知，最大子序列和為26，序列是{15、-2、13}。
在整個過程中，我們只用指針遍歷了一遍序列，并且做了簡單的記錄，所以動態(tài)規(guī)劃算法的時間復(fù)雜度是O(n)。
總結(jié)
窮舉法1：
算法思想：窮舉所有子序列，找最大的。
時間復(fù)雜度：O(n3)
缺點：包含大量重復(fù)計算。
窮舉法2：
算法思想：在某點開始的所有子序列中，找最大的。
時間復(fù)雜度：O(n2)
缺點：同樣包含重復(fù)計算。
分治法：
算法思想：利用可分解、遞歸的性質(zhì)，采用分治策略。
時間復(fù)雜度：O(nlgn)
動態(tài)規(guī)劃法：
算法思想：采用了動態(tài)規(guī)劃的方法。
時間復(fù)雜度：O(n)
