最大連續子序列和問題
給定k個整數的序列{N1,N2,…,Nk }，其任意連續子序列可表示為{ Ni, Ni+1, …, Nj }，其中 1 <= i <= j <= k。最大連續子序列是所有連續子序中元素和最大的一個，例如給定序列{ -2, 11, -4, 13, -5, -2 }，其最大連續子序列為{11,-4,13}，最大連續子序列和即為20。
注：為友善起見，如果所有整數均為負數，則最大子序列和為0。
解決這樣一個問題是一個很有趣的過程，我們可以嘗試着從複雜度比較高的算法一步一步地推出複雜度較低的算法。
算法一：
時間複雜度：O(N^3)
其代碼：
對于此種算法，其主要方法是窮舉法，即求出該序列所有子序列的序列和，然後取最大值即可。
算法二：
時間複雜度：O(N^2)
對于這種方法，歸根究底還是屬于窮舉法，其間接地求出了所有的連續子序列的和，然後取最大值即可。
那麼，這裡，我們需要對比一下前面兩種算法，為什麼同樣都是窮舉法，但算法一的時間複雜度遠高于算法二的時間複雜度？
算法二相較于算法一，其優化主要展現在減少了很多重複的操作。
對于A-B-C-D這樣一個序列，
算法一在計算連續子序列和的時候，其過程為：
A-B、A-C、A-D、B-C、B-D、C-D
而對于算法二，其過程為：
其過程貌似是一樣的，但是算法一的複雜就在于沒有充分利用前面已經求出的子序列和的值。
舉個例子，算法一在求A-D連續子序列和的值時，其過程為A-D = A-B + B-C + C-D；
而對于算法二，A-D連續子序列和的求值過程為A-D = A-C+C-D；
這樣，算法二充分利用了前面的計算值，這樣就大大減少了計算子序列和的步驟。
算法三：遞歸法（分治法）
時間複雜度：O(NlogN)
易知，對于一數字序列，其最大連續子序列和對應的子序列可能出現在三個地方。或是整個出現在輸入資料的前半部（左），或是整個出現在輸入資料的後半部（右），或是跨越輸入資料的中部進而占據左右兩半部分。前兩種情況可以通過遞歸求解，第三種情況可以通過求出前半部分的最大和（包含前半部分的最後一個元素）以及後半部分的最大和（包含後半部分的第一個元素）而得到，然後将這兩個和加在一起即可。
其實作代碼為：
現在對上面的代碼進行相關說明：
Center變量所确定的值将處理序列分割為兩部分，一部分為Center前半部，一部分為Center+1後半部。
在上文，我們提到，最大連續子序列的出現位置有三種情況。
對于前兩種情況，我們根據遞歸特性，可以得到：
而對于第三種情況，我們需要先求出前半部包含最後一個元素的最大子序列：
然後，再求出後半部包含第一個元素的最大子序列：
最後，我們隻需比較這三種情況所求出的最大連續子序列和，取最大的一個，即可得到需要求解的答案。
我們在介紹這個算法的開始，就已經提到了其時間複雜度，現在做一個推導：
令T(N)是求解大小為N的最大連續子序列和問題所花費的時間。
當N==1時，T(1) = 1；
當N>1時，T(N) = T(N/2) + O(N)；
有數學推導公式，我們可以得到：
T(N) = NlogN + N =O(NlogN)。
算法四：動态規劃法
時間複雜度：O(N)
終于到了動态規劃的部分了，這麼一步一步走來，感受到了算法的無窮魅力。那麼如何用動态規劃來處理這個問題？
首先，我們重溫将一個問題用動态規劃方法處理的準則：
“最優子結構”、“子問題重疊”、“邊界”和“子問題獨立”。
在本問題中，我們可以将子序列與其子子序列進行問題分割。
最後得到的狀态轉移方程為：
MaxSum[i] = Max{ MaxSum[i-1] + A[i], A[i]};
在這裡，我們不必設定數組MaxSum[]。
代碼實作：
在本代碼實作中，ThisSum持續更新，同時整個過程，隻對資料進行了一次掃描，一旦A[i]被讀入處理，它就不再需要被記憶。（聯機算法）
小結：
整個過程是一個思想的選擇問題，從最初的窮舉法，到分治法，再到動态規劃法。算法設計思想的靈活選擇是處理一個實際問題的關鍵。
<a href="#" target="_blank"></a>
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)