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

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

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

左邊最大子序列

右邊最大子序列

跨中點(diǎn)的最大子序列

其中，步驟3分別求出包含左側(cè)和右側(cè)包含中點(diǎn)端點(diǎn)的最大子序列，求和即是結(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ù)開(kāi)始為是否到達(dá)遞歸基準(zhǔn)的if判斷語(yǔ)句，然后分別是兩個(gè)遞歸語(yǔ)句，執(zhí)行步驟①②。對(duì)于遞歸而言，遞歸語(yǔ)句后邊的語(yǔ)句暫時(shí)不執(zhí)行，從遞歸語(yǔ)句處直接返回遞歸函數(shù)開(kāi)始進(jìn)行遞歸，在該遞歸語(yǔ)句處向內(nèi)遞歸，直到到達(dá)基準(zhǔn)語(yǔ)句，執(zhí)行return跳出遞歸。遞歸語(yǔ)句計(jì)算出maxLeftSum和maxRightSum。

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

最后，求出最大者即可。

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

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

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

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

整個(gè)過(guò)程類(lèi)似二叉樹(shù)的每一個(gè)節(jié)點(diǎn)都長(zhǎng)三個(gè)不同大小的桃子，從根節(jié)點(diǎn)遞歸到最下層的樹(shù)葉，比較三個(gè)桃子的大小，摘取一個(gè)，再摘取同輩的其他節(jié)點(diǎn)的桃子。依次向上摘，總體呈現(xiàn)從總到分，再?gòu)姆值娇偟囊粋€(gè)過(guò)程。

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

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

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

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

參考書(shū)上的方法，使用規(guī)律遞推的方式，計(jì)算T（N）。簡(jiǎ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）

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