程序員面試100題：求子數(shù)組的最大和

1.題目 ? ?輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。

?????? 例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，因此輸出為該子數(shù)組的和18。

2.算法初級(jí)分析 ? ?剛開始接觸，我們肯定會(huì)想用遍歷數(shù)組求和來解決問題，如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。但顯然那樣做的話沒有什么算法含量，過于暴力了，沒有編程藝術(shù)的氣息。并且題目要求時(shí)間復(fù)雜度為O(n)，長(zhǎng)度為n的數(shù)組有 ((n+1)*n)/2 個(gè)子數(shù)組（即為O(n2) ），而且求一個(gè)長(zhǎng)度為n的數(shù)組的和的時(shí)間復(fù)雜度為O(n)，因此這種思路的時(shí)間是O( n3 )。

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;???

??}
?}
?return maximum;

}?

第二種解法：

int?maxsum(int?a[n])??????
{??
????int?max=a[0];??????
????int?sum=0;??
????for(int?j=0;j=0)?????
????????????sum+=a[j];??
????????else?????
????????????sum=a[j];?
????????if(sum>max)??
????????????max=sum;??
????}??
????return?max;??
}??
??
int?main()??
{??
????int?a[]={1,-2,3,10,-4,7,2,-5};??
????cout<<maxsum(a)<<endl;??
????return?0;??
}

第三種解法： 動(dòng)態(tài)規(guī)劃：設(shè)sum[i] 為前i個(gè)元素中，包含第i個(gè)元素且和最大的連續(xù)子數(shù)組，result 為已找到的子數(shù)組中和最大的。對(duì)第i+1個(gè)元素有兩種選擇：做為新子數(shù)組的第一個(gè)元素、放入前面找到的子數(shù)組。
sum[i+1] = max(a[i+1], sum[i] + a[i+1])
result = max(result, sum[i])
3.編程之美的代碼 下面給出《Data structures and Algorithm analysis in C》中4種實(shí)現(xiàn)

//Algorithm?1:時(shí)間效率為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;kMaxSum)??
????????????????MaxSum=ThisSum;??
????????}??
????????return?MaxSum;??
}??
??
//Algorithm?2:時(shí)間效率為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;jMaxSum)??
????????????????MaxSum=ThisSum;??
????????}??
????}??
????return?MaxSum;??
}??
??
//Algorithm?3:時(shí)間效率為O(n*log?n)??
//算法3的主要思想：采用二分策略，將序列分成左右兩份。??
//那么最長(zhǎng)子序列有三種可能出現(xiàn)的情況，即??
//【1】只出現(xiàn)在左部分.??
//【2】只出現(xiàn)在右部分。??
//【3】出現(xiàn)在中間，同時(shí)涉及到左右兩部分。??
//分情況討論之。??
static?int?MaxSubSum(const?int?A[],int?Left,int?Right)??
{??
????int?MaxLeftSum,MaxRightSum;??????????????//左、右部分最大連續(xù)子序列值。對(duì)應(yīng)情況【1】、【2】??
????int?MaxLeftBorderSum,MaxRightBorderSum;??//從中間分別到左右兩側(cè)的最大連續(xù)子序列值，對(duì)應(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;iMaxRightBorderSum)??
????????????????MaxRightBorderSum=RightBorderSum;??
????????}??
????????int?max1=MaxLeftSum>MaxRightSum?MaxLeftSum:MaxRightSum;??
????????int?max2=MaxLeftBorderSum+MaxRightBorderSum;??
????????return?max1>max2?max1:max2;??
}??
??
//Algorithm?4:時(shí)間效率為O(n)??
//同上述第一節(jié)中的思路3、和4。??
int?MaxSubsequenceSum(const?int?A[],int?N)??
{??
????int?ThisSum,MaxSum,j;??
????ThisSum=MaxSum=0;??
????for(j=0;jMaxSum)??
????????????MaxSum=ThisSum;??
????????else?if(ThisSum<0)??
????????????ThisSum=0;??
????}??
????return?MaxSum;??
}