浙江大學-數據結構-應用實例：最大子列和問題-1.3.1(補前面的章節)

來自專欄 Excalibur5 人贊了文章

應用實例：最大子列和問題

所謂最大子列和問題，給定N個整數的序列，我們要求這個函數的最大值，這是一個什麼函數呢？就是從 到 連續的一段子列的和，那我們對N個整數來說，有很多這樣連續的子列，我們要求的是所有連續子列和裡面最大的那個，如果這個和它是負數的話，那我們最後就返回0作為結束，要解決這個問題呢？其實有好多好多不同的演算法，一個最直接最暴力的辦法就是我把所有的連續子列和全部都算出來，然後從中找最大的那個，這就是我們的第一個演算法

輸入是整數序列，以及整數序列的個數，總的來說，是有二重循環，最外層循環i對應的是子列左端的位置，是從 開始，然後j對的是子列和的右邊的位置，一直到 為止，所以j總是大於等於i的，從i開始計數，

然後在這個雙重循環裡面呢，我們就開始暴力的求這個子列和， 所以我們還需要一重循環叫做k, k從i一直加到j, ThisSum就是當前的和，從 一直加到 ,加完了以後看一下，這個和如果比最大的和要大的話，那麼我們更新一下這個最大和，

這個演算法其實很不聰明，我們先從i=0開始，加了1個數，然後在算第二個子列的時候，我們又從0加到1，算第三個子列的時候，從0，1加到2，最後一個循環是從0加到n-1,大概是這麼一個過程，然後i往上進了一位，我們從1開始加，加2個，一直加到n-1,然後i=2的時候又繼續，我們看到中間有個很大的問題，當我們知道當前從i到j的和的時候，我們要計算下一個j的時候，我有必要從頭開始往後加嗎？沒有必要，所以當j增加了1的時候，我們其實只要在前面那個i到j的部分和後面加一個元素就好了，我們其實是完全沒有必要要那個k循環的，這個k循環完全是多餘的，我只要在前面j的基礎上加一個元素就好了，這樣就有了我們的演算法2，

看到時間複雜度為 就要下意識把它改進成NlogN呢？

先把數組一分為二，遞歸的去解決左邊的問題，得到左邊的最大子列和，遞歸的去解決右邊的問題，得到右邊的最大子列和，然後就可以了嗎？然後我們就可以說這兩個數中間最大的一個就一定是結論嗎？那可不一定，還有一種情況，還有一種情況就是跨越邊界的最大子列和，把這3個結果找到以後，那我們真的可以說，最後的結果一定是這3個數中間最大的那一個，

為了能更好的理解這個演算法，我們來看一個具體的例子，比如說給了8個數字，第一步把它從中間一分為二，然後遞歸的先解決左半邊，再遞歸的進入左半邊的時候呢，繼續把它一分為二，繼續的遞歸到左半邊，然後繼續分

分的時候我們會得到最大子列和，

左邊應該返回6，然後你知道可以怎麼解決右半邊的問題了，

返回11作為最終的解，看上去也不是很複雜，教科書裡面有，大家可以自己去看，難點在於怎麼樣分析它的演算法複雜度，這個演算法真的是nlogn嗎？分析這種遞歸的演算法略微有些難度，當我解決整個問題有n個數字的時候，如果我的複雜度把它記作T(n)的話，那麼我得到這半邊的複雜度就是T(n/2),因為我的規模減半了，而我是怎麼得到中間跨邊界最大子列和的呢？我們的做法就是從中間開始，往左邊掃描，然後往右邊掃描，每一個元素都被掃描了一次，所以得到這個結果的複雜度應該是O(N)的常數倍，由此我們就得到了T(N)的遞推公式，

一直往下展開，展開到T裡面的數等於1為止，過了k步以後，右邊是每展開一層就多一個cN,展開k步以後就是ckN, 其中k和N是什麼關係呢？就是N/2,除了k次以後，最終它會得到1，它可能不一定整除成1，但是也差不多，道理是一樣的，所以2^k就是N,k就是logN,以2為底的logN,所以在分析複雜度的時候，我們就有了兩項，一項是O(N),一項是O(NlogN),當兩個複雜度加在一起的時候，我們取的是比較大的那一項，於是我們就得到了整個演算法的複雜度O(NlogN),

這仍然不是我們最快的演算法，

只有一個for循環，是線性的時間複雜度，這個必須是可能得到的最快演算法了，因為無論如何總得把每個元素看一遍，一個演算法效率這麼高，一般是有副作用的，正確性不是特別明顯，也就是別人要理解這個程序到底是怎麼工作的略微有點困難，為了更好的理解它還是先來看一個例子，最開始仍然有ThisSum當前的子列和，MaxSum是最大的子列和，都初始化為0，然後我們就進入了很重要的for循環，第一件事做了什麼呢？就是當前的子列和，把當前這個數加起來，於是我們看到的第一個數字是-1, -1並不能使當前的最大和變大，所以這一塊就跳過去了，重要的是這條，如果當前的子列和是負的，那麼我們就直接把它拋棄，把當前子列和重新歸0，把-1直接扔掉，子列和重新歸0，為什麼可以這麼做呢？因為我們是要求連續的子列和，所以如果當前的子列和到這裡，下一步我們要順著往後去求和的，如果現在的和是負數的話，往後面不管加什麼數，它都只能讓後面的數字越變越小，不可能越變越大，所以我還不如從頭加起，因為它不可能使後面的和增大，所以就拋棄之，然後進入for循環的下一輪，讀進來3，當前的3比MaxSum要大，於是當前的最大子列和我們先記一下，更新為3，然後因為ThisSum是正的，所以進入下一個循環，再加一個-2，於是當前和是+1，+1比MaxSum要小，所以最大和是不動的，而ThisSum當前的和也不會被拋棄，因為它是+1，總有可能是後面的和變的更大的，於是我們繼續進入下一輪，讀下一個數字4，果然把下一個數變大了，現在當前和是5，5比現在的最大和要大，所以最大和要更新一下，變成了5，為什麼這個演算法叫在線處理呢？我們看到整個的處理過程是什麼樣的呢?一個數字一個數字的讀進來，而我的輸入如果說到現在為止，

我突然停住，後面的輸入不讀了，那麼現在這個程序就應該返回5作為當前的最大子列和，而這個結果是對的，就對於前4個數字而言，這個結果是對的，這個就叫做在線處理，現在是5，繼續往下加一個-6，於是當前的子列和變成了-1，是負的了，就把它拋棄掉，

重新歸0，開始考慮下一個，下一個是1，什麼都沒變化，再下一個是6，加起來等於7，它比原來的最大和要大了，所以最大和更新一下，

然後再加一項，進來是-1，什麼都沒改變，輸入結束了，跳出來返回的結果是7，所以為什麼它會快呢？充分的利用了一旦發現當前子列和是負的話，它其實就沒有用了，直接把它拋棄掉，掃描後面就可以，

四種演算法的時間比較