摘要：下面進(jìn)行簡單的作圖分析注意到，遞歸函數(shù)從外層，沿著計算的路徑，經(jīng)過三次遞歸調(diào)用函數(shù)，到達(dá)基準(zhǔn)，在基準(zhǔn)層分別計算遞歸函數(shù)內(nèi)部的三部分左側(cè)最大子序列與右側(cè)最大子序列的和，并利用求出最大者返回。

問題：給定整數(shù)序列，求解其中最大子序列（連續(xù)的序列）。

利用“分治”和遞歸的思想求解，在《數(shù)據(jù)結(jié)構(gòu)與算法分析（Java語言描述）》Page29，作者給出了具體的java代碼。
總體思路是，原序列的子序列存在于三處，左、右和跨中點。將序列從中點分割，分別用遞歸求出

左邊最大子序列

右邊最大子序列

跨中點的最大子序列

其中，步驟3分別求出包含左側(cè)和右側(cè)包含中點端點的最大子序列，求和即是結(jié)果。
這樣最后三者中的最大者即為序列的最大子序列。

//添加了求三數(shù)最大值的函數(shù)
public class MaxSubsequence {

    public static int maxSubSum3(int[] a) {
        return maxSumRec(a,0,a.length-1);
    }
    
    private static int maxSumRec(int[] a,int left,int right) {
        if(left==right) {
            if(a[left]>0)
                return a[left];
            else
                return 0;
        }
        
        int center =(left+right)/2;
        int maxLeftSum=maxSumRec(a, left, center);     //遞歸1
        int maxRightSum=maxSumRec(a, center+1, right); //遞歸2
        
        int maxLeftBorderSum=0,leftBorderSum=0;
        for(int i=center;i>=left;i--) {
            leftBorderSum+=a[i];
            if(leftBorderSum>maxLeftBorderSum)
                maxLeftBorderSum=leftBorderSum;            
        }
        
        int maxRightBorderSum=0,rightBorderSum=0;
        for(int i=center+1;i<=right;i++) {
            rightBorderSum+=a[i];
            if(rightBorderSum>maxRightBorderSum)
                maxRightBorderSum=rightBorderSum;            
        }
        
        return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);            
    }
    
    public static int max3(int a,int b,int c) {
        int temp=a>b?a:b;
        int max3=temp>c?temp:c;
        return max3;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr={4,-3,5,-2,-1,2,6,-2};
        int maxSubSum=maxSubSum3(arr);
        System.out.println("the maxSubSum of array arr is:"+maxSubSum);
    }

}

程序中，maxSumRec為遞歸函數(shù)，函數(shù)開始為是否到達(dá)遞歸基準(zhǔn)的if判斷語句，然后分別是兩個遞歸語句，執(zhí)行步驟①②。對于遞歸而言，遞歸語句后邊的語句暫時不執(zhí)行，從遞歸語句處直接返回遞歸函數(shù)開始進(jìn)行遞歸，在該遞歸語句處向內(nèi)遞歸，直到到達(dá)基準(zhǔn)語句，執(zhí)行return跳出遞歸。遞歸語句計算出maxLeftSum和maxRightSum。

函數(shù)中，遞歸語句后邊的部分計算步驟③，在for循環(huán)中，固定中點端點，分別向左右兩側(cè)循環(huán)求和，利用if語句來更新包含中心端點的maxLeftBorderSum和maxRightBorderSum。兩個變量求和即是③的最大子序列。

最后，求出最大者即可。

啟發(fā)：使用遞歸的時候，需要在遞歸語句前邊，提前設(shè)置好到達(dá)基準(zhǔn)的條件（if，return/break），以便適時完成遞歸，跳出遞歸函數(shù)。

注意到，該段程序的兩條遞歸語句出現(xiàn)在同一個函數(shù)內(nèi)，起初我對遞歸的具體執(zhí)行順序理解錯誤，以為步驟①的遞歸執(zhí)行得出maxLeftSum時，之后的步驟③語句并不會執(zhí)行。實際進(jìn)行程序調(diào)試后，發(fā)現(xiàn)，該段程序雖然看起來相對簡潔，但在執(zhí)行時，會執(zhí)行不必要的語句，執(zhí)行邏輯并不明了。

下面進(jìn)行簡單的作圖分析：

注意到，遞歸函數(shù)從外層，沿著計算maxLeft的路徑，經(jīng)過三次遞歸調(diào)用maxSumRec函數(shù)，到達(dá)基準(zhǔn)，在基準(zhǔn)層分別計算遞歸函數(shù)內(nèi)部的三部分maxLeft、maxRight、左側(cè)最大子序列與右側(cè)最大子序列的和maxLeftBorderSum+maxRightBorderSum，并利用max3求出最大者返回。然后再從基準(zhǔn)層向上，計算上一層maxRightSum，然后依次規(guī)律，逐步向上計算，最后計算出整個遞歸函數(shù)的maxLeft、maxRight和左右和，最后再執(zhí)行max3函數(shù)，返回三者的最大值，得到最終的最大子序列和。

整個過程類似二叉樹的每一個節(jié)點都長三個不同大小的桃子，從根節(jié)點遞歸到最下層的樹葉，比較三個桃子的大小，摘取一個，再摘取同輩的其他節(jié)點的桃子。依次向上摘，總體呈現(xiàn)從總到分，再從分到總的一個過程。

程序主要運行部分在maxSumRec函數(shù)，分為if判斷基準(zhǔn)語句、兩條遞歸語句、兩個for計算半側(cè)邊界最大子序列語句。若序列元素個數(shù)為N，T（N）為該算法的運行時間。

在maxSumRec函數(shù)中，不管N為多少，if基準(zhǔn)語句部分總是運行固定的常數(shù)時間。

若N=1，為基準(zhǔn)情況，if語句執(zhí)行，return返回結(jié)果，后續(xù)部分不再執(zhí)行，因此，T（1）=1。

若N≠1，則后續(xù)的程序必須執(zhí)行。兩個for循環(huán)中，索引0~N-1的元素都被接觸一次，運行時間為O（N）。if基準(zhǔn)語句、與if等縮進(jìn)的幾條賦值語句運行時間為常量，與O（N）比可忽略。剩余為兩條遞歸語句，每條語句執(zhí)行時間為T（N/2）,因為左/右最大子序列求解，都是處理N/2大小的子序列。總的運行時間T（N）=2T（N/2）+O（N）。

參考書上的方法，使用規(guī)律遞推的方式，計算T（N）。簡化O（N）為N，并假設(shè)N為2的冪。T（2）=2×2，T（4）=4×3，T（8）=8×4，T（16）=16×5，若N=2^k，則T（N）=N(logN+1)=O（N log N）

總體而言，對于計算序列的最大子序列而言，書中的本算法略顯麻煩，后續(xù)會進(jìn)行其他簡潔方法的補(bǔ)充，本文借此算法來深入理解遞歸的過程。