程序員編程藝術(shù)：第七章、求連續(xù)子數(shù)組的最大和
作者：July。
出處：http://blog.csdn.net/v_JULY_v 。
前奏
- 希望更多的人能和我一樣，把本狂想曲系列中的任何一道面試題當做一道簡單的編程題或一個實質(zhì)性的問題來看待，在閱讀本狂想曲系列的過程中，希望你能盡量暫時放下所有有關(guān)面試的一切包袱，潛心攻克每一道“編程題”，在解決編程題的過程中，好好享受編程帶來的無限樂趣，與思考帶來的無限激情。--By@July_____。
- 原狂想曲系列已更名為：程序員編程藝術(shù)系列。原狂想曲創(chuàng)作組更名為編程藝術(shù)室。編程藝術(shù)室致力于以下三點工作：1、針對一個問題，不斷尋找更高效的算法，并予以編程實現(xiàn)。2、解決實際中會碰到的應(yīng)用問題，如第十章、如何給10^7個數(shù)據(jù)量的磁盤文件排序。3、經(jīng)典算法的研究與實現(xiàn)。總體突出一點：編程，如何高效的編程解決實際問題。歡迎有志者加入。
第一節(jié)、求子數(shù)組的最大和
3.求子數(shù)組的最大和
題目描述：
輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。
數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。
求所有子數(shù)組的和的最大值。要求時間復(fù)雜度為O(n)。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，
因此輸出為該子數(shù)組的和18。
分析：這個問題在各大公司面試中出現(xiàn)頻率之頻繁，被人引用次數(shù)之多，非一般面試題可與之匹敵。單憑這點，就沒有理由不入選狂想曲系列中了。此題曾作為本人之前整理的微軟100題中的第3題，至今反響也很大。ok，下面，咱們來一步一步分析這個題：
1、求一個數(shù)組的最大子數(shù)組和，如此序列1, -2, 3, 10, -4, 7, 2, -5，我想最最直觀也是最野蠻的辦法便是，三個for循環(huán)三層遍歷，求出數(shù)組中每一個子數(shù)組的和，最終求出這些子數(shù)組的最大的一個值。
記Sum[i, …, j]為數(shù)組A中第i個元素到第j個元素的和（其中0 <= i <= j < n），遍歷所有可能的Sum[i, …, j]，那么時間復(fù)雜度為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最終存放的是所有子數(shù)組的和。也就是編程之美上所說的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;
- //其實要處理全是負數(shù)的情況，很簡單，如稍后下面第3點所見，直接把這句改成："int sum=a[0]"即可
- //也可以不改，當全是負數(shù)的情況，直接返回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}; //測試全是負數(shù)的用例
- cout<<maxSum(a,8)<<endl;
- return 0;
- }
-
- /*-------------------------------------
- 解釋下：
- 例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，
- 那么最大的子數(shù)組為3, 10, -4, 7, 2，
- 因此輸出為該子數(shù)組的和18。
-
- 所有的東西都在以下倆行，
- 即：
- b ： 0 1 -1 3 13 9 16 18 13
- sum： 0 1 1 3 13 13 16 18 18
-
- 其實算法很簡單，當前面的幾個數(shù)，加起來后，b<0后，
- 把b重新賦值，置為下一個元素，b=a[i]。
- 當b>sum，則更新sum=b;
- 若b<sum，則sum保持原值，不更新。。July、10/31。
- ----------------------------------*/
3、不少朋友看到上面的答案之后，認為上述思路2的代碼，沒有處理全是負數(shù)的情況，當全是負數(shù)的情況時，我們可以讓程序返回0，也可以讓其返回最大的那個負數(shù)，下面便是前幾日重寫的，修改后的處理全是負數(shù)情況（返回最大的負數(shù)）的代碼：
- //copyright@ July
- //July、updated，2011.05.25。
- #include <iostream.h>
- #define n 4 //多定義了一個變量
-
- int maxsum(int a[n])
- //于此處，你能看到上述思路2代碼（指針）的優(yōu)勢
- {
- int max=a[0]; //全負情況，返回最大數(shù)
- int sum=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 main()
- {
- int a[]={-1,-2,-3,-4};
- cout<<maxsum(a)<<endl;
- return 0;
- }
4、DP解法的具體方程：@ flyinghearts：設(shè)sum[i] 為前i個元素中，包含第i個元素且和最大的連續(xù)子數(shù)組，result 為已找到的子數(shù)組中和最大的。對第i+1個元素有兩種選擇：做為新子數(shù)組的第一個元素、放入前面找到的子數(shù)組。
sum[i+1] = max(a[i+1], sum[i] + a[i+1])
result = max(result, sum[i])
擴展：
1、如果數(shù)組是二維數(shù)組，同樣要你求最大子數(shù)組的和列?
2、如果是要你求子數(shù)組的最大乘積列?
3、如果同時要求輸出子段的開始和結(jié)束列?
第二節(jié)、Data structures and Algorithm analysis in C
下面給出《Data structures and Algorithm analysis in C》中4種實現(xiàn)。
- //感謝網(wǎng)友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;
- for(i=0;i<N;i++)
- {
- ThisSum=0;
- for(j=i;j<N;j++)
- {
- ThisSum+=A[j];
- if(ThisSum>MaxSum)
- MaxSum=ThisSum;
- }
- }
- return MaxSum;
- }
-
- //Algorithm 3:時間效率為O(n*log n)
- //算法3的主要思想：采用二分策略，將序列分成左右兩份。
- //那么最長子序列有三種可能出現(xiàn)的情況，即
- //【1】只出現(xiàn)在左部分.
- //【2】只出現(xiàn)在右部分。
- //【3】出現(xiàn)在中間，同時涉及到左右兩部分。
- //分情況討論之。
- static int MaxSubSum(const int A[],int Left,int Right)
- {
- int MaxLeftSum,MaxRightSum; //左、右部分最大連續(xù)子序列值。對應(yīng)情況【1】、【2】
- int MaxLeftBorderSum,MaxRightBorderSum; //從中間分別到左右兩側(cè)的最大連續(xù)子序列值，對應(yīng)case【3】。
- int LeftBorderSum,RightBorderSum;
- int Center,i;
- if(Left == Right)Base Case
- if(A[Left]>0)
- return A[Left];
- else
- 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)
- //同上述第一節(jié)中的思路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)
- ThisSum=0;
- }
- return MaxSum;
- }
本章完。