首页 > 代码库 > 应用实例——最大子列和问题
应用实例——最大子列和问题
题目描述:给定N个整数的序列{A1,A2,...,AN},求函数f(i,j)=max{0,ΣAk(i<=k<=j)}的最大值
算法1:
1 int MaxSubseqSum1(int A[],int N){ 2 int ThisSum,MaxSum=0; 3 int i,j,k; 4 for(i=0;i<N;i++){//i是子列左端位置 5 for(j=i;j<N;j++){//j是子列右端位置 6 ThisSum=0; 7 for(k=i;k<j;k++){//ThisSum是A[i]到A[j]的子列和 8 ThisSum+=A[k]; 9 if(ThisSum>MaxSum)//如果刚得到的这个子列和更大 10 MaxSum=ThisSum;//则更新结果 11 } 12 } 13 } 14 return MaxSum; 15 }
由程序结构可知,此算法的时间复杂度T(N)=O(N3)[有三层嵌套的for循环]
算法2:
1 int MaxSubseqSum1(int A[],int N){ 2 int ThisSum,MaxSum=0; 3 int i,j; 4 for(i=0;i<N;i++){//i是子列左端位置 5 ThisSum=0; 6 for(j=i;j<N;j++){//j是子列右端位置 7 ThisSum+=A[j];//对于相同的i,不同的j,只要在j-1次循环的基础上累加1项即可 8 if(ThisSum>MaxSum)//如果刚得到的这个子列和更大 9 MaxSum=ThisSum;//则更新结果 10 } 11 } 12 } 13 return MaxSum; 14 }
由程序结构可知,此算法的时间复杂度T(N)=O(N2)[有两层嵌套的for循环]
算法3:分而治之
算法思路:将一个比较大而复杂的问题切分成比较小的模块,然后分头解决,最后把结果合并起来。
工作流程:[假设待解决的问题放在一个数组里面]
- 第一步:划分:按照平衡子问题的原则,将序列(a1,a2,...,an)划分成长度相同的两个序列(a1,...,an/2)和(an/2+1,...,an),则会出现一下三种情况:
- a1,...,an的最大字段和=a1,...,an/2的最大字段和①
- a1,...,an的最大字段和=an/2+1,...,an的最大字段和②
- a1,...,an的最大字段和=Σak(i<=k<=j),且1<=i<=n/2,n/2+1<=j<=n③
- 第二步:求解子问题:对于划分阶段的情况①和②可递归求解,情况③需要分别计算左右两端的最大子列和,然后两个之和为情况③的最大子列和。
- 第三步:合并:比较在划分阶段三种情况下的最大子列和,取三者关系中的较大者为原问题的解。
例:给定一个数组[4,-3,5,-2,-1,2,6,-2]
先从中间将其一分为二
然后递归地先解决左半边,继续将其一分为二
继续地递归到左半边,继续分
针对最后的一次划分,左边的最大子列和为4,右边最大子列和为-3,小于左边,会返回0,则跨越边界的最大子列和为4。依此类推,得到最终的划分结果为:
int MaxSubseqSum3(int a[],int left,int right){//求序列a[left]~a[right]的最大子列和 int sum=0,midSum=0,leftSum=0,rightSum=0; int center,s1,s2,lefts,rights; if(left==right)//如果序列长度为1,直接求解 sum=a[left]; else{ center=(left+right)/2;//划分 leftSum=MaxSubseqSum3(a,left,center);//对应情况①,递归求解 rightSum=MaxSubseqSum3(a,center,right);//对应情况②,递归求解 s1=0;lefts=0;//以下对应情况③,先求解s1 for(int i=center;i>=left;i--){ lefts+=a[i]; if(lefts>s1) s1=lefts; } s2=0;rights=0;//再求解s2 for(int j=center+1;j<=right;j++){ rights+=a[j]; if(rights>s2) s2=rights; } midSum=s1+s2;//计算情况③的最大子列和 if(midSum<leftSum)//合并解,取较大者 sum=lefstSum; else sum=midSum; if(sum<rightSum) sum=rightSum; } return sum; }
划分之后,每个程序执行的数据规模是N/2,对应划分得到的情况①和情况②,需要分别进行递归求解,对应情况③,两个并列for循环的时间复杂性是O(N),所以存在如下的递推式:
- T(N)=1 当N=1时;
- T(N)=2T(N/2)+c·N 当N>1时;
T(N)=2T(N/2)+c·N=2[2T(N/4)+c·N/2]+c·N
=22T(N/22)+2c·N
=2kO(1)+ck·N,其中N/2k=1
=O(Nlog2N)
由程序结构可知,此算法的时间复杂度T(N)=O(Nlog2N)
算法4:在线处理
“在线”的意思是指每输入一个数据就进行即时处理,在任何一个地方中止输入,算法都能正确给出当前的解。
1 int MaxSubseqSum4(int A[],int N){ 2 int ThisSum,MaxSum=0; 3 int i; 4 ThisSum=MaxSum=0; 5 for(i=0;i<N;i++){ 6 ThisSum+=A[i];//向右累加 7 if(ThisSum>MaxSum) 8 MaxSum=ThisSum;//发现更大和则更新当前结果 9 else if(ThisSum<0)//如果当前子列和为负 10 ThisSum=0;//则不可能使得后面的部分和增大,抛弃之 11 } 12 return MaxSum; 13 }
由程序结构可知,此算法的时间复杂度T(N)=O(N)[只有一个for循环,而且if-else的复杂度都为常数]
复杂度越小,理解起来越困难
例:
①第一个数字为-1,由于它不能使后面的部分增大,因此将ThisSum重置为0,MaxSum=0
②MaxSum=3,ThisSum=3
③ThisSum=1>0,不会被重置为0
④ThisSum=5,MaxSum=5,最大和更新
⑤ThisSum=-1<0,被抛弃,将ThisSum重置为0
⑥ThisSum=1,MaxSum=5
⑦ThisSum=7,MaxSum=7,最大和更新
⑧ThisSum=6,MaxSum=7,最大和未改变
所以得到的最大子列和为7。
算法 | 1 | 2 | 3 | 4 |
时间复杂度 | O(N3) | O(N2) | O(NlogN) | O(N) |
N=10 | 0.00103 | 0.00045 | 0.00066 | 0.00034 |
N=100 | 0.47015 | 0.01112 | 0.00486 | 0.00063 |
N=1000 | 448.77 | 1.1233 | 0.05843 | 0.00333 |
N=10000 | NA | 111.13 | 0.68631 | 0.03042 |
N=100000 | NA | NA | 8.0113 | 0.29832 |
应用实例——最大子列和问题