程式員程式設計藝術：第七章、求連續子數組的最大和

前奏

第一節、求子數組的最大和

3.求子數組的最大和

題目描述：

輸入一個整形數組，數組裡有正數也有負數。

數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。

求所有子數組的和的最大值。要求時間複雜度為O(n)。

例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，

是以輸出為該子數組的和18。

分析：這個問題在各大公司面試中出現頻率之頻繁，被人引用次數之多，非一般面試題可與之匹敵。單憑這點，就沒有理由不入選狂想曲系列中了。此題曾作為本人之前整理的微軟100題中的第3題，至今反響也很大。ok，下面，咱們來一步一步分析這個題：

      1、求一個數組的最大子數組和，如此序列1, -2, 3, 10, -4, 7, 2, -5，我想最最直覺也是最野蠻的辦法便是，三個for循環三層周遊，求出數組中每一個子數組的和，最終求出這些子數組的最大的一個值。

記Sum[i, …, j]為數組A中第i個元素到第j個元素的和（其中0 <= i <= j < n），周遊所有可能的Sum[i, …, j]，那麼時間複雜度為O（N^3）：

//本段代碼引自程式設計之美 int MaxSum(int* A, int n) {  int maximum = -INF;   int sum=0;     for(int i = 0; i < n; i++)  {   for(int j = i; j < n; j++)   {    for(int k = i; k <= j; k++)    {     sum += A[k];    }    if(sum > maximum)     maximum = sum;    sum=0;   //這裡要記得清零，否則的話sum最終存放的是所有子數組的和。也就是程式設計之美上所說的bug。多謝蒼狼。   }  }  return maximum; } 

      2、其實這個問題，在我之前上傳的微軟100題，答案V0.2版[第1-20題答案]，便直接給出了以下O（N）的算法：

//copyright@ July 2010/10/18  

//updated，2011.05.25.  

#include <iostream.h>  

int maxSum(int* a, int n)  

{  

    int sum=0;  

    //其實要處理全是負數的情況，很簡單，如稍後下面第3點所見，直接把這句改成："int sum=a[0]"即可  

    //也可以不改，當全是負數的情況，直接傳回0，也不見得不行。  

    int b=0;  

    for(int i=0; i<n; i++)  

    {  

        if(b<0)           //...  

            b=a[i];  

        else  

            b+=a[i];  

        if(sum<b)  

            sum=b;  

    }  

    return sum;  

}  

int main()  

    int a[10]={1, -2, 3, 10, -4, 7, 2, -5};  

    //int a[]={-1,-2,-3,-4};  //測試全是負數的用例  

    cout<<maxSum(a,8)<<endl;  

    return 0;  

/*------------------------------------- 

解釋下： 

例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5， 

那麼最大的子數組為3, 10, -4, 7, 2， 

是以輸出為該子數組的和18。 

所有的東西都在以下倆行， 

即： 

b  ：  0  1  -1  3  13   9  16  18  13   

sum：  0  1   1  3  13  13  16  18  18 

其實算法很簡單，目前面的幾個數，加起來後，b<0後， 

把b重新指派，置為下一個元素，b=a[i]。 

當b>sum，則更新sum=b; 

若b<sum，則sum保持原值，不更新。。July、10/31。 

----------------------------------*/  

      3、不少朋友看到上面的答案之後，認為上述思路2的代碼，沒有處理全是負數的情況，當全是負數的情況時，我們可以讓程式傳回0，也可以讓其傳回最大的那個負數，下面便是前幾日重寫的，修改後的處理全是負數情況（傳回最大的負數）的代碼：

//copyright@ July  

//July、updated，2011.05.25。  

#define n 4           //多定義了一個變量  

int maxsum(int a[n])    

//于此處，你能看到上述思路2代碼（指針）的優勢  

    int max=a[0];       //全負情況，傳回最大數  

    for(int j=0;j<n;j++)  

        if(sum>=0)     //如果加上某個元素，sum>=0的話，就加  

            sum+=a[j];  

        else     

            sum=a[j];  //如果加上某個元素，sum<0了，就不加  

        if(sum>max)  

            max=sum;  

    return max;  

    int a[]={-1,-2,-3,-4};  

    cout<<maxsum(a)<<endl;  

      4、DP解法的具體方程：@ flyinghearts：設sum[i] 為前i個元素中，包含第i個元素且和最大的連續子數組，result 為已找到的子數組中和最大的。對第i+1個元素有兩種選擇：做為新子數組的第一個元素、放入前面找到的子數組。

sum[i+1] = max(a[i+1], sum[i] + a[i+1])

result = max(result, sum[i])

擴充：

1、如果數組是二維數組，同樣要你求最大子數組的和列?

2、如果是要你求子數組的最大乘積列?

3、如果同時要求輸出子段的開始和結束列?

第二節、Data structures and Algorithm analysis in C

下面給出《Data structures and Algorithm analysis in C》中4種實作。

//感謝網友firo  

//July、2010.06.05。  

//Algorithm 1:時間效率為O(n*n*n)  

int MaxSubsequenceSum1(const int A[],int N)  

    int ThisSum=0 ,MaxSum=0,i,j,k;  

    for(i=0;i<N;i++)  

        for(j=i;j<N;j++)  

        {  

            ThisSum=0;  

            for(k=i;k<j;k++)  

                ThisSum+=A[k];  

            if(ThisSum>MaxSum)  

                MaxSum=ThisSum;  

        }  

        return MaxSum;  

//Algorithm 2:時間效率為O(n*n)  

int MaxSubsequenceSum2(const int A[],int N)  

    int ThisSum=0,MaxSum=0,i,j,k;  

        ThisSum=0;  

            ThisSum+=A[j];  

    return MaxSum;  

//Algorithm 3:時間效率為O(n*log n)  

//算法3的主要思想：采用二分政策，将序列分成左右兩份。  

//那麼最長子序列有三種可能出現的情況，即  

//【1】隻出現在左部分.  

//【2】隻出現在右部分。  

//【3】出現在中間，同時涉及到左右兩部分。  

//分情況讨論之。  

static int MaxSubSum(const int A[],int Left,int Right)  

    int MaxLeftSum,MaxRightSum;              //左、右部分最大連續子序列值。對應情況【1】、【2】  

    int MaxLeftBorderSum,MaxRightBorderSum;  //從中間分别到左右兩側的最大連續子序列值，對應case【3】。  

    int LeftBorderSum,RightBorderSum;  

    int Center,i;  

    if(Left == Right)Base Case  

        if(A[Left]>0)  

            return A[Left];  

            return 0;  

        Center=(Left+Right)/2;  

        MaxLeftSum=MaxSubSum(A,Left,Center);  

        MaxRightSum=MaxSubSum(A,Center+1,Right);  

        MaxLeftBorderSum=0;  

        LeftBorderSum=0;  

        for(i=Center;i>=Left;i--)  

            LeftBorderSum+=A[i];  

            if(LeftBorderSum>MaxLeftBorderSum)  

                MaxLeftBorderSum=LeftBorderSum;  

        MaxRightBorderSum=0;  

        RightBorderSum=0;  

        for(i=Center+1;i<=Right;i++)  

            RightBorderSum+=A[i];  

            if(RightBorderSum>MaxRightBorderSum)  

                MaxRightBorderSum=RightBorderSum;  

        int max1=MaxLeftSum>MaxRightSum?MaxLeftSum:MaxRightSum;  

        int max2=MaxLeftBorderSum+MaxRightBorderSum;  

        return max1>max2?max1:max2;  

//Algorithm 4:時間效率為O(n)  

//同上述第一節中的思路3、和4。  

int MaxSubsequenceSum(const int A[],int N)  

    int ThisSum,MaxSum,j;  

    ThisSum=MaxSum=0;  

    for(j=0;j<N;j++)  

        ThisSum+=A[j];  

        if(ThisSum>MaxSum)  

            MaxSum=ThisSum;  

        else if(ThisSum<0)  

}