参考紫书8.1章节。
最大连续和问题
在给定序列中找到最大连续和，该问题最简单的解答思路是将所有子序列的和求出，并找到最大值，但如果序列长度较大或序列中元素的值较大，计算需要的时间都将大幅增加。因此需要使用更优化的算法。以下列举四种算法，使用函数maxsum求出最大连续和，数组A存放给定序列，n表示序列长度。
暴力求解
int maxsum(int *A,int n){
int maxs=A[1]; //初始最大值
for(int i=1;i<=n;i++) //找到所有子序列
for(int j=i;j<=n;j++){
int sum=0;
for(int k=i;k<=j;k++)
sum+=A[k];
maxs=max(maxs,sum);
}
return maxs;
}
求出所有子序列的和，逐个比较找出最大值，时间复杂度为n^3，当序列长度较长时，运算时间很可能超出要求。
通过前缀和求出子序列的和
int maxsum(int *A,int n){
//求出前缀和
int S[n+1];
S[0]=0;
for(int i=1;i<=n;i++)
S[i]=S[i-1]+A[i];
//根据前缀和求出子序列的和
int maxs=A[1];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
maxs=max(maxs,S[j]-S[i-1]); //注意i-1
return maxs;
}
使用前缀和将免去使用循环计算子序列和的部分，因此时间复杂度减少到n^2，但在n过大时仍然需要较多时间。
分治法
int maxsum(int *A,int n,int l,int r){ //返回数组在区间[l,r)中的最大连续和
if(l==r-1) return A[l]; //若只有一个元素，返回该元素
int m=l+(r-l)/2; //将区间[l,r)分为区间[l,m)和[m,r)
int maxs=max(maxsum(A,n,l,m),maxsum(A,n,m,r)) //递归求解
int L,R,all;
all=0;L=A[m-1];
for(int i=m-1;i>=l;i++) //从分界点开始往左的最大连续和
L=max(L,all+=A[i]);
all=0;R=A[m];
for(int i=m;i<y;i++) //从分界点开始往右的最大连续和
R=max(R,all+=A[i]);
return max(L+R,maxs); //比较最大值
}
将序列划分为左右两个区间，并利用递归求出左区间，右区间的最大值，利用循环求出合并区间的最大值，最终比较得出结果。对这一题目使用分治法时maxsum函数使用了递归和一重循环，最终时间复杂度为nlogn，时间复杂度随n的增加而增加的幅度更小了。
最优解
int maxsum(int *A,int n){
int S[n+1];
S[0]=0;
for(int i=1;i<=n;i++) //计算前缀和
S[i]=S[i-1]+A[i];
int maxs=A[1],mixS=S[1]; //mixS为目前出现的最小前缀和
for(int i=1;i<=n;i++){
maxs=max(maxs,S[i]-mixS);
mixS=mix(mixa,S[i]);
}
return maxs;
}
同样使用前缀和计算子序列的和，在前面的解法中，子序列的和=S[j]-S[i-1]，只要将最小的S[i-1]记录下来，就可以直接用S[j]减去最小的S[i-1]，得到子序列的最大和，于是又省略了一种循环，时间复杂度被降到n。
根据n的取值判断算法是否合理
假设机器速度时每秒10^8次基本运算，1秒内能解决最大问题规模n
若题目范围中n的可取值较大，我们就不太可能使用前几种时间复杂度的程序解答，若n的取值较小，则可以使用。
网友评论