问题描述:
一个有N个整数元素的一维数组(A[0],A[1],...A(n-1),它包含很多子数组,求子数组之和的最大值,当数组元素全部为负的时候,有两种处理办法,第一种是返回0,第二种是返回数组中最大的负数。
解法1:
使用暴力法,假设最大的一段数组为A[i],...,A[j],则对i:=0~n-1 j:=i~n-1,遍历一遍,求出最大的Sum(i,j)即可
解法2:
使用分治法,数组(A[0],A[1],...A(n-1)分为长度相等的两段数组(A[0],...,A[n/2])以及(A[n/2+1],...,A[n-1]),分别求出这两段数组各自的最大子段和,则原数组(A[0],A[1],...A(n-1)的最大子段和分为3种情况
1)(A[0],A[1],...A(n-1)的最大子段和与(A[0],...,A[n/2])的相同
2)(A[0],A[1],...A(n-1)的最大子段和与(A[n/2+1],...,A[n-1])的相同
3)(A[0],A[1],...A(n-1)的最大子段和跨过(A[0],...,A[n/2])与(A[n/2+1],...,A[n-1])
解法3:
使用动态规划法,假设A[0],A[1],...A(n-1)的最大子段为A[i],...,A[j],则有以下3种情况
1)当0=i=j的时候,元素A[0]本身构成和最大的一段
2)当0=i<j的时候,和最大的一段以A[0]开头
3)当0<i时候,元素A[0]跟和最大的一段没有关系
则原始问题A[0],A[1],...A(n-1)的解All[0]=max{A[0],A[0]+Start[1],ALL[1]}
程序说明:
下面的程序中,针对数组全部为负的情况的处理(处理1:直接返回0,处理2:返回数组中最大的负数)定义了两种情况,分别对应于定义了RETURN_ZERO和RETURN_MAXMINUS这两种情况
//定义了RETURN_ZERO说明处理全部为负数的数组时候返回0
#define RETURN_ZERO
#ifdef RETURN_ZERO
/*******************************解法一:蛮力法*****************************
依次计算A[0],A[0..1],...A[0..n-1],A[1],A[1..2]...A[1..n-1],A[2],A[2..3],...
A[2..n-1]...并返回最大的值maximum
****************************************************************************/
int MaxSum1(int *A,int length){
int maximum=0; //子数组和最大值
int sum; //子数组和
for(int i=0;i<length;i++){
sum=0;
for(int j=i;j<length;j++){
sum+=A[j];
if(sum>maximum)
maximum=sum;
}
}
return maximum;
}
/*******************************解法二:分治法*******************************
数组(A[0],A[1],...A(n-1)分为长度相等的两段数组(A[0],...,A[n/2])以及(A[n/2+1],
...,A[n-1]),分别求出这两段数组各自的最大子段和,则原数组(A[0],A[1],...A(n-1)
的最大子段和分为3种情况:
1)(A[0],A[1],...A(n-1)的最大子段和与(A[0],...,A[n/2])的相同
2)(A[0],A[1],...A(n-1)的最大子段和与(A[n/2+1],...,A[n-1])的相同
3)(A[0],A[1],...A(n-1)的最大子段和跨过(A[0],...,A[n/2])与(A[n/2+1],...,A[n-1])
*****************************************************************************/
int MaxSum2(int *A,int left,int right){
if(left==right){
return max(A[left],0);
}
int middle=(left+right)/2;
//求(A[0],...A[n/2-1])中子数组包含A[n/2-1]的最大值
int lmaximum=0;
int lsum=0;
for(int i=middle;i>=left;i--){
lsum+=A[i];
if(lsum>lmaximum)
lmaximum=lsum;
}
//求(A[n/2],...,A[n-1])中子数组包含A[n/2]的最大值
int rmaximum=0;
int rsum=0;
for(int i=middle+1;i<=right;i++){
rsum+=A[i];
if(rsum>rmaximum)
rmaximum=rsum;
}
return max(lmaximum+rmaximum,max(MaxSum2(A,left,middle),MaxSum2(A,middle+1,right)));
}
/******************************解法三:动态规划**********************************
假设A[0],A[1],...A(n-1)的最大子段为A[i],...,A[j],则有以下3种情况,
1)当0=i=j的时候,元素A[0]本身构成和最大的一段
2)当0=i<j的时候,和最大的一段以A[0]开头
3)当0<i时候,元素A[0]跟和最大的一段没有关系
则原始问题A[0],A[1],...A(n-1)的解All[0]=max{A[0],A[0]+Start[1],ALL[1]}
*********************************************************************************/
//从尾到首动态规划(编程之美2.14的思想)
int MaxSum3(int *A,int length){
int nStart=0;
int nAll=0;
for(int i=length-1;i>=0;i--){
nStart=max(0,A[i]+nStart);
nAll=max(nStart,nAll);
}
return nAll;
}
//从首到尾动态规划(编程珠玑8.4思想)
int MaxSum3_v2(int *A,int length){
int nStart=0;
int nAll=0;
for(int i=0;i<length;i++){
nStart=max(0,A[i]+nStart);
nAll=max(nStart,nAll);
}
return nAll;
}
#endif
//定义了RETURN_MAXMINUS说明处理全部为负数的数组时候返回最大负数
//#define RETURN_MAXMINUS
#ifdef RETURN_MAXMINUS
/*******************************解法一:蛮力法*****************************
依次计算A[0],A[0..1],...A[0..n-1],A[1],A[1..2]...A[1..n-1],A[2],A[2..3],...
A[2..n-1]...并返回最大的值maximum
****************************************************************************/
int MaxSum1(int *A,int length){
int maximum=-100000000; //子数组和最大值
int sum; //子数组和
for(int i=0;i<length;i++){
sum=0;
for(int j=i;j<length;j++){
sum+=A[j];
if(sum>maximum)
maximum=sum;
}
}
return maximum;
}
/*******************************解法二:分治法*******************************
数组(A[0],A[1],...A(n-1)分为长度相等的两段数组(A[0],...,A[n/2])以及(A[n/2+1],
...,A[n-1]),分别求出这两段数组各自的最大子段和,则原数组(A[0],A[1],...A(n-1)
的最大子段和分为3种情况:
1)(A[0],A[1],...A(n-1)的最大子段和与(A[0],...,A[n/2])的相同
2)(A[0],A[1],...A(n-1)的最大子段和与(A[n/2+1],...,A[n-1])的相同
3)(A[0],A[1],...A(n-1)的最大子段和跨过(A[0],...,A[n/2])与(A[n/2+1],...,A[n-1])
*****************************************************************************/
int MaxSum2(int *A,int left,int right){
if(left==right){
return A[left];
}
int middle=(left+right)/2;
//求(A[0],...A[n/2-1])中子数组包含A[n/2-1]的最大值
int lmaximum=-100000000;
int lsum=0;
for(int i=middle;i>=left;i--){
lsum+=A[i];
if(lsum>lmaximum)
lmaximum=lsum;
}
//求(A[n/2],...,A[n-1])中子数组包含A[n/2]的最大值
int rmaximum=-100000000;
int rsum=0;
for(int i=middle+1;i<=right;i++){
rsum+=A[i];
if(rsum>rmaximum)
rmaximum=rsum;
}
return max(lmaximum+rmaximum,max(MaxSum2(A,left,middle),MaxSum2(A,middle+1,right)));
}
/******************************解法三:动态规划**********************************
假设A[0],A[1],...A(n-1)的最大子段为A[i],...,A[j],则有以下3种情况,
1)当0=i=j的时候,元素A[0]本身构成和最大的一段
2)当0=i<j的时候,和最大的一段以A[0]开头
3)当0<i时候,元素A[0]跟和最大的一段没有关系
则原始问题A[0],A[1],...A(n-1)的解All[0]=max{A[0],A[0]+Start[1],ALL[1]}
*********************************************************************************/
//从尾到首动态规划(编程之美2.14的思想)
int MaxSum3(int *A,int length){
int nStart=A[length-1];
int nAll=A[length-1];
for(int i=length-2;i>=0;i--){
nStart=max(A[i],A[i]+nStart);
nAll=max(nStart,nAll);
}
return nAll;
}
//从首到尾动态规划(编程珠玑8.4思想)
int MaxSum3_v2(int *A,int length){
int nStart=A[0];
int nAll=A[0];
for(int i=1;i<length;i++){
nStart=max(A[i],A[i]+nStart);
nAll=max(nStart,nAll);
}
return nAll;
}
#endif
#define MAIN
#ifdef MAIN
int main(){
int a[6]={1,-2,3,5,-3,2};
int b[6]={0,-2,3,5,-1,2};
int c[6]={-9,-2,-3,-5,-3};
#ifdef RETURN_ZERO
cout<<"****************蛮力法结果:****************"<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum1(a,6)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum1(b,6)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回0) "<<MaxSum1(c,5)<<endl;
cout<<"*************分治法结果:*******************"<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum2(a,0,5)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum2(b,0,5)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回0) "<<MaxSum2(c,0,4)<<endl;
cout<<"*****************动态规划结果:**************"<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum3(a,6)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum3(b,6)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回0) "<<MaxSum3(c,5)<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum3_v2(a,6)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum3_v2(b,6)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回0) "<<MaxSum3_v2(c,5)<<endl;
#endif
#ifdef RETURN_MAXMINUS
cout<<"****************蛮力法结果:****************"<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum1(a,6)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum1(b,6)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回-2) "<<MaxSum1(c,5)<<endl;
cout<<"*************分治法结果:*******************"<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum2(a,0,5)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum2(b,0,5)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回-2) "<<MaxSum2(c,0,4)<<endl;
cout<<"*****************动态规划结果:**************"<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum3(a,6)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum3(b,6)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回-2) "<<MaxSum3(c,5)<<endl;
cout<<"a 的子数组和的最大值是(正确结果应该返回8) "<<MaxSum3_v2(a,6)<<endl;
cout<<"b 的子数组和的最大值是(正确结果应该返回9) "<<MaxSum3_v2(b,6)<<endl;
cout<<"c 的子数组和的最大值是(正确结果应该返回-2) "<<MaxSum3_v2(c,5)<<endl;
#endif
system("PAUSE");
return 0;
}
#endif