【0】README

0.1） source code and text description are from data structure and alg analysis ；
0.2） there are 4 methods solving maximum sum of subsequence， but the fourth proves to be the best one , the 3rd deserves learning for ‘Divide and Conquer’；
0.3） what’s the maximum sum of subsequence ？

---

Method1）嘗試窮舉所有可能情況：

源代碼： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p18.c

我們由內(nèi)到外分析上述算法的時間復雜度（Analysis）：

• A1）最內(nèi)層循環(huán)
  
• A2）中間層循環(huán)
  
• A3）最外層循環(huán)
  
  代碼演示分析步驟：
  

算法描述（Description）：

• D1）顯然 i， j 分別作為小數(shù)組（我暫且這么叫）的下上限（這個上下限通過兩個for循環(huán)來實現(xiàn)），然后指針k在里面滑動，計算累加和；
• D2）顯然算法的最內(nèi)層循環(huán)過分地耗時了。因為之前算了的， 我還要重新算一次。如第一步要計算 A[2] ~ A[5] 的累加和，我第二步還要算 A[2]~A[6] 的累加和，所以說第二步是重復了第一步的大多數(shù)工作，因為A[2] ~ A[5]的累加和在第一步已經(jīng)算過了；

---

Method2）我們撤除一個for循環(huán)來避免立方運行時間：

源代碼： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p19.c

時間復雜度分析

代碼演示分析步驟：

算法描述（Description）：

• D1）顯然 i 作為小數(shù)組的上限，下限始終是末尾元素（這個上下限通過兩個for循環(huán)來實現(xiàn)）；
• D2）在小數(shù)組中，我們并沒有用for循環(huán)來遍歷所有元素，因為那是無效的，而是用一個if語句來判斷是否 在遍歷某元素 A[j] 后， sum是增加還是減少，增加，我們就賦值給maxsum， 減少，不賦值就是了，從而撤銷掉一個for循環(huán)；

---

Method3）采用分治思想來解決（分治是干貨）

源代碼： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p20.c

算法描述：其思想是把問題分成兩個大致相等的子問題，然后遞歸地對它們進行求解，這是“分”部分；“治”階段 將兩個子問題的解合并到一起并可能再做些少量的附加工作，最后得到整個問題的解；

• 在我們的例子中（求最大子序列和的問題），最大子序列和可能出現(xiàn)在三個地方——或者整個出現(xiàn)在輸入數(shù)據(jù)的左半部、或者整個出現(xiàn)在右半部、或者跨越輸入數(shù)據(jù)的中部從而占據(jù)左右兩半部分；
• 如何求其解呢？ 前兩種情況，可以遞歸求解，第3中情況的最大和可以通過求出前半部分的最大和（包含前半部分的最后一個元素）以及 后半部分的最大和（包含后半部分的第一個元素）而得到。然后將這兩個和加在一起；

考慮以下輸入：

• 代碼演示分析步驟
  
  

算法流程演示

Attention）：

• A1）如（0，7）表示（left， right）， 而center = （left + right） ／２　
• A2）顯然算法把 整個序列分割成若干了子序列，各子序列和進行比較，求出序列最大值；　其中最經(jīng)典的是 max3（）函數(shù)的調(diào)用，它返回的是兩個子節(jié)點的序列和 和 其最近父節(jié)點序列和的最大值。然后回溯回去，一步一步進行（１,２,３．．．　表示返回的遞歸回溯的次序）
• A3）這個函數(shù) maxSubSum_3（）是如何返回序列的最大和的——主要還是依賴與 max3（）函數(shù)的存在。
• Attention）看到?jīng)]有？　該函數(shù)的遞歸次序類似于二叉樹的 后序遞歸 idea（上圖中的二叉樹）。

---

Method4）利用聯(lián)機算法解決最大子序列和問題

源代碼： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p21.c

時間復雜度：T(N)=O(N)
代碼演示步驟

Attention）：

• 顯然，最大子序列和所在的子序列不包括任意”子子序列“為負的情況，因為負就相當于做減法；當thisSum 小于 0 時，令thisSum=0, 即排除了子序列和為負的情況；

算法解說（Commentary）：

• C1）優(yōu)點： 它只對數(shù)據(jù)進行一次掃描，一旦A[i]被處理，就不需要再記憶了；
• C2）在任意時刻， 算法都能對他已經(jīng)讀入的數(shù)據(jù)給出子序列問題的正確答案；
• C3）具有這種特性的算法叫——聯(lián)機算法（online algorithm）；
• C4）僅需要線性時間運行的聯(lián)機算法幾乎是完美的算法；

What’s the online algorithm ?

• 如果在任何時刻，算法都能對它已經(jīng)讀入的數(shù)據(jù)給出子序列問題的正確答案，具有這種特性的算法叫做 聯(lián)機算法；
  因此如果數(shù)組在磁盤或磁帶上，它就可以被順序讀入，在主存中不必存儲數(shù)組的任何部分。所以這個算法是一個幾乎完美的 聯(lián)機算法；
• 【百度百科】
  在任意時刻算法對要操作的數(shù)據(jù)只讀入（掃描）一次，一旦被讀入并處理，它就不需要再 被記憶了。而在此處理過程中算法能對它已經(jīng)讀入的數(shù)據(jù)立即給出相應子序列問題的正確答案。具有這種特性的算法叫做聯(lián)機算法（on-line algorithm）；

Complementary）分治法 與 動態(tài)規(guī)劃

• C1）分治法： 分治法是將問題分為一系列獨立小問題，然后分別找到每個小問題的解決方案，然后把每部分的解決方案合并起來，適用于具有同類解決方案的子問題 的求解；
• C2）動態(tài)規(guī)劃：動態(tài)規(guī)劃是將問題分為一系列 相互聯(lián)系 的子問題，求解一個子問題可能要用到已經(jīng)求解過的子問題的解，子問題具有重疊性，適合具有重疊子問題性質(zhì)的問題求解；

總結

以上是生活随笔為你收集整理的最大子序列和问题的解（共4种，层层推进）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。