最大連續(xù)子列和問(wèn)題

Q： 給定N個(gè)整數(shù)的序列{A_1,A_2, …, A_N}，求函數(shù) f(i,j)=max{0, \sum_{k=i}^{j}{A_k}}

A1：暴力解法。遍歷計(jì)算全部子列和，然后從中再去尋找最大的那一個(gè)。

int maxSubseqSum(int A[], int N){
    int thisSum, maxSum = 0;
    int i, j, k;
    for( i = 0; i < N; i++ ){           // i是子列左側(cè)位置
        for( j = i; j < N; j++ ){       // j是子列右端位置
            thisSum = 0;                // thisSum是A[i]到A[j]的子列和
            for( k = i; k <= j; k++ )   
                thisSum += A[k];
            if( thisSum > maxSum )      // 如果剛得到的這個(gè)子列和更大
                maxSum = thisSum;       // 則更新結(jié)果
        }
    }
    return maxSum;
}

時(shí)間復(fù)雜度：T(N) = O(N^3)

A2：對(duì)A1的改進(jìn)。A1的方法很笨，但是笨在哪里呢？其在j循環(huán)內(nèi)層，每次對(duì)thisSum進(jìn)行歸零，然后再?gòu)念^進(jìn)行累加操作；但實(shí)際上，對(duì)于相同的i，不同的j的情況，我們只需要不停維護(hù)thisSum的值，使其和maxSum做比較即可，而完全不用每次都從最頂端加起。

也就是說(shuō)，k循環(huán)是完全沒(méi)有必要的。

int maxSubseqSum(int A[], int N){
    int thisSum, maxSum = 0;
    int i, j, k;
    for( i = 0; i < N; i++ ){           // i是子列左側(cè)位置
        thisSum = 0;                    // thisSum是A[i]到A[j]的子列和
        for( j = i; j < N; j++ ){       // j是子列右端位置
            thisSum += A[j];            // 對(duì)于相同的i，不同的j，只要繼續(xù)維護(hù)thisSum的值即可
            if( thisSum > maxSum )      // 如果剛得到的這個(gè)子列和更大
                maxSum = thisSum;       // 則更新結(jié)果
        }
    }
    return maxSum;
}

時(shí)間復(fù)雜度：T(N) = O(N^2)

A3：分治思想。盡管 O(N^2) 已經(jīng)比 O(N^3) 提高了一個(gè)量級(jí)，但是 O(N^2) 的算法效率仍然比較低下。當(dāng)實(shí)現(xiàn)了一個(gè)O(N^2)的算法時(shí)，本能的應(yīng)該去思考，如何將其優(yōu)化為O(NlogN)的算法。

在本題中，可以考慮使用分治思想，對(duì)整個(gè)數(shù)組進(jìn)行取半，然后依次遞歸求解，從而實(shí)現(xiàn)O(NlogN)的時(shí)間復(fù)雜度。需要注意的是，本題中簡(jiǎn)單的分而治之不能囊括全部情況，還需要考慮跨越算法二分邊界的子列和。

int maxSubseqSum(int arr[], int l, int r){
    if(l == r) return arr[l] > 0 ? arr[l] : 0;      // 遞歸到底，返回正整數(shù)結(jié)果，否則返回0
    int mid = (l + r) / 2;                          // 取中間值，分
    int maxLeft = getMaxNum(arr, l, mid);           // 分治的過(guò)程，遞歸求最大值
    int maxRight = getMaxNum(arr, mid + 1, r);

    int maxLeftSum = 0, tempLeftSum = 0;            // merge的過(guò)程，計(jì)算跨越中間值的最大序列
    for (int i = mid; i >= l; i--){                 // 由中間向左側(cè)掃描數(shù)組
        tempLeftSum += arr[i];                      // 依次累加求和
        if (tempLeftSum > maxLeftSum)               // 如果發(fā)現(xiàn)有連續(xù)的更大值，則記錄下來(lái)
            maxLeftSum = tempLeftSum;
     }

    int maxRightSum = 0, tempRightSum = 0;
    for (int i = mid + 1; i <= r; i++){             // 由中間向右側(cè)掃描數(shù)組
        tempRightSum += arr[i];                     // 依次累加求和
        if (tempRightSum > maxRightSum){            // 如果有連續(xù)的更大值，記錄下來(lái)
            maxRightSum = tempRightSum;
        
    }
    // 在最后，對(duì)左側(cè)最值，右側(cè)最值，跨越中間值的最值求最大者，即為最大連續(xù)子列和
    return Math.max(maxLeftSum + maxRightSum, Math.max(maxLeft, maxRight));
}

在這個(gè)分治的過(guò)程中，遞歸到底求最值沒(méi)什么好解釋的；重點(diǎn)在于merge的過(guò)程。

在具體進(jìn)行merge時(shí)，由于是從中間值開始向兩側(cè)掃描的，且每逢更大值則記錄下來(lái)，就可以保證最后maxLeftSum + maxRightSum的值為一個(gè)連續(xù)的子列和，也正是我們所需要的跨越中間值的最長(zhǎng)子列。

因此，用該值與左側(cè)最值，右側(cè)最值求max，則能夠得到我們想要的結(jié)果，也就是最大子列和。

時(shí)間復(fù)雜度： T(N) = 2 T(N/2) + cN，其中T(1)=O(1)

               = 2 [2 T(N/2^2) + c N/2] + cN

               = 2^kO(1) + c k N     其中 N/2^k=1     

               = O(N log N) 

A4：在線處理算法，線性算法

在線的意思是指，每輸入一個(gè)數(shù)據(jù)就進(jìn)行即時(shí)處理，在任何一個(gè)地方終止輸入，算法都能正確給出當(dāng)前的解。

int maxSubseqSum(int A[], int N){
    int thisSum, maxSum = 0;
    int i;
    for( i = 0; i < N; i++ ){           
        thisSum += A[i];            // 遍歷整個(gè)數(shù)組，依次向右累加
        if( thisSum > maxSum )      
            maxSum = thisSum;       // 發(fā)現(xiàn)更大和，則更新當(dāng)前結(jié)果
        else if(thisSum < 0)        // 如果當(dāng)前子列和為負(fù)
            thisSum = 0;            // 則不可能使后面的部分和更大，拋棄之
    }
    return maxSum;
}

時(shí)間復(fù)雜度：T(N) = O(N)

這是能夠想到的效率最高的算法了，因?yàn)樵僭趺凑f(shuō)，也需要把整個(gè)數(shù)組掃描一遍才能得到結(jié)果。在線處理算法由于其即時(shí)處理的性質(zhì)，保證了其可怕的效率。