最大连续和

最新推荐文章于 2021-04-27 21:42:28 发布

OFShare

最新推荐文章于 2021-04-27 21:42:28 发布

阅读量381

点赞数 1

本文链接：https://blog.csdn.net/Cui_csdn/article/details/71518202

版权

//给出一个长度为n的序列A1,A2,...，An,求最大连续和

//使用枚举 时间复杂度O(n^3)

best=A[1];					//初始最大值
for(int i=1;i<=n;++i)
{
	for(int j=i;j<=n;++j)	//检查连续子序列A[i],...,A[j]
	{
		int sum=0;
		for(int k=i;k<=j;++k)
			sum+=A[k];		//累加元素和
		if(sum>best)
			best=sum;		//更新最大值
	}
}

//设Si=A1+A2+...+Ai,则Ai+Ai+1+...+Aj=Sj-Si-1 (连续子序列的和等于两个前缀之差) 时间复杂度O(n^2)

S[0]=0;
for(int i=1;i<=n;++i)	//递推前缀和
	S[i]=S[i-1]+A[i];
	
for(int i=1;i<=n;++i)
	for(int j=i;j<=n;++j)
		best=max(best,S[j]-S[i-1]);	//更新最大值

//分治法 时间复杂度O(nlogn)

int maxsum(int *A,int x,int y)	//返回数组在[x,y)中的最大连续和
{
	int maxs;
	if(y-x==1)
		return A[x];
	int m=x+(y-x)/2;							//第一步：划分[x,m)和[m,y)
	int maxs=max(maxsum(A,x,m),maxsum(A,m,y));	//第二步:递归求解
	
	int v,L,R;									//第三步:合并
	v=0;L=A[m-1];
	for(int i=m-1;i>=x;--i)
		L=max(L,v+=A[i]);						//从分界点开始往左的最大连续和L
	v=0;R=A[m];
	for(int i=m;i<y;++i)
		R=max(R,v+=A[i]);						//从分界点开始往右的最大连续和R
		
	return max(maxs,L+R);						//把子问题的解与L和R比较	
}