最大子序列和求解過程

問題來曆

 該問題最早出現在布朗大學Grenander面對的一個模式比對的問題，問題的最初形式是給定nxn的實數數組，求出矩形子數組的最大總和。最大綜合子數組是數字圖像中某種特定模式的最大似然估計量，因為二維問題求解需要太多時間，是以将它簡化為一維問題進而深入了解其結構。這個問題的解決經曆了四種複雜度的算法最終得到解決，一開始的算法的時間複雜度為 O(n3) O ( n 3 ) ,第一次改良之後的時間複雜度為 O(n2) O ( n 2 ) ，再改良為 O(nlogn) O ( n l o g n ) ,最終改良為 O(n) O ( n ) 。從一開始解決規模為100 000的問題需要15天到最後隻需要5毫秒，提升是顯而易見的。

 在這篇部落格中将會從 O(n3) O ( n 3 ) 開始逐漸得到 O(n) O ( n ) ，在這裡先定義一組測試資料x[0..9]如下

31−415926−535897−96−93−2384 31 − 41 59 26 − 53 58 97 − 96 − 93 − 23 84

最終的結果是x[2..6]，和為187。知道資料跟結果我們就開始我們的解題吧

O(n3) O ( n 3 ) 解法

  O(n3) O ( n 3 ) 解法很簡單，就是我們看到這道題的時候潛意識中想象到的方法，也叫做暴力破解法。用語言描述就是對所有滿足 0≤i≤j<n 0 ≤ i ≤ j < n 的(i,j)整數對進行疊代，對每一個整數對計算x[i..j]的和，然後檢驗總和是否大于迄今為止的最大綜合，用僞代碼表示就是

tmax=0
for i=[0,n]
    for j=[i,n]
        sum=0
        for k=[i,j]
            sum+=x[k]
        tmax=max(tmax,sum)
           

将僞碼轉換成可運作的Python程式：

tmax=
x=[,-,,,-,,,-,-,]
for i in range(,):
    for j in range(i,):
        sum=
        for k in range(i,j+):
            sum+=x[k]
        tmax=max(tmax,sum)
print tmax
           

可以得到正确的結果為187。這種解法是符合思維邏輯的但是對于計算機來說并不友好，通過觀察我們很容易發現其實第三層循環是不必要的。

O(n2) O ( n 2 ) 的兩種解法

 一般來說都不會想到 O(n3) O ( n 3 ) 的解法，都是從 O(n2) O ( n 2 ) 開始，從 O(n3) O ( n 3 ) 到 O(n2) O ( n 2 ) 有兩種改良的方法，都是為了去除第三套循環。第一個改良的關注點是，x[i..j]的總和與前面已計算出的總和x[i..j-1]的總和密切相關，改良後的僞代碼

tmax=0
for i=[0,n)
    sum=0
    for j=[i,n)
        sum+=x[j]
        tmax=max(tmax,sum)
           

可執行的python代碼

tmax=
x=[,-,,,-,,,-,-,]
for i in range(,):
    sum=
    for j in range(i,):
        sum+=x[j]
        tmax=max(tmax,sum)
print tmax
           

第二種改良方法是通過通路在外循環執行之前就已建構的資料結構的方式在内循環中計算總和。假設一個數組sumarr的第i個元素包含了x[0..i]中各個數的累加和，是以x[i..j]中各個數的總和可以通過計算sumarr[j]-sumarr[i-1]得到，該方法改良後的僞代碼為

sumarr[-1]=0
for i=[0,n)
    sumarr[i]=sumarr[i-1]+x[i]
tmax=0
for i=[0,n)
    for j=[i,n)
        sum+=x[j]
        tmax=max(tmax,sum)
           

這裡轉化為實際代碼的時候存在取數組第-1個數的問題，解決的方法就是把原來的數組加長一個數。

可運作的python代碼

tmax=
x=[,-,,,-,,,-,-,]
sumarr=[]*
for i in range(,):
    sumarr[i+]=sumarr[i]+x[i]
for i in range(,):
    for j in range(i,):
        sum=sumarr[j+]-sumarr[i]
        tmax=max(tmax,sum)
print tmax
           

O(nlogn) O ( n l o g n ) 解法

  O(nlogn) O ( n l o g n ) 算法利用的是分治政策，也就是，要解決規模為n的問題，可遞歸地解決兩個規模近似為 n/2 n / 2 的子問題，然後對它們的答案進行合并以得到整個問題的答案。

 使用分治政策解決的思路是，把數組分為ab兩部分，然後求出a部分以及b部分的最大子序列和為 ma m a ， mb m b ，還有一個最重要的是求出橫跨ab部分的最大子序列的和為 mc m c ，然後比較三個之中最大的值。根據這個指導思想可以得出以下代碼

float mss(l,u)
    if (l>u)
        return 0
    if (l==u)
        return max(0,x[1])
    m=(l+u)/2
    lmax=sum=0
    for (i=m;i>=1;i--)
        sum+=x[i]
        lmax=max(lmax,sum)

    rmax=sum=0
    for i=(m,u]
        sum+=x[i]
        rmax=max(rmax,sum)
    return max(lmax+rmax,mss(l,m),mss(m+1,u))
           

轉換為可執行的python代碼為

x=[,-,,,-,,,-,-,]
def mss(l,u):
    if (l>u):
    return 
    if (l==u):
        return max(,x[])
    m=(l+u)/

    lmax=sum=
    for i in (range(,m))[::-]:
        sum+=x[i]
        lmax=max(lmax,sum)

    rmax=sum=

    for i in range(m,u+):
        sum+=x[i]
        rmax=max(rmax,sum)
    return max(lmax+rmax,mss(l,m),mss(m+,u))

if __name__=='__main__':
    print mss(,)
           

O(n)解法 O ( n ) 解 法

 這種解法應該是最廣為流傳的最佳解法，也就是一般人說的掃描算法，解題的思路是，從數組最左端開始掃描，一直到最右端，并幾下所遇到的總和最大的子序列。最重要的原理就是，前i個元素中，最大總和子序列要麼在前i-1個元素中（設為tmax），要麼其結束位置為i（設為fmax）。

 計算fmax有一個巧妙的方法，不需要從頭開始計算結束位置為i的最大子序列，而是利用結束位置為i-1的最大子序列進行計算，具體實作如下

tmax=0
fmax=0
for i=[0,n)
    fmax=max(fmax+x[i],0)
    tmax=max(tmax,fmax)
           

該代碼需要細細體會。關鍵點在于fmax，fmax肯定是包含最後一個數的最大的子序列，而tmax是目前位置總和最大的子序列。

很容易轉換為python代碼

tmax=
fmax=
x=[,-,,,-,,,-,-,]


for i in range(,):
    fmax=max(fmax+x[i],)
    tmax=max(tmax,fmax)
print tmax
           

總結

 這是我看《程式設計珠玑》的時候第一次感受到一個好的算法居然可以讓程式提速得如此誇張，還有一個原因是這也是面試或者機試的常考題，也許以前在一些競賽書上能夠看到最快速的解法，但能夠看到一個算法從 O(n3) O ( n 3 ) 到 O(n) O ( n ) 的進化簡直是一種享受。而且在這其中還有一個小故事是，當得到 O(nlogn) O ( n l o g n ) 算法的時候，《程式設計珠玑》的作者和他身邊的人都以為這是最佳解法，在一個會議上公布這個成果的時候，一個與者這隻花了幾分鐘就想到了 O(n) O ( n ) 的解法，可以看出算法設計也是要看靈感的。好的算法往往更加簡潔而不容易出錯。

參考資料《程式設計珠玑》