最大连续和

今天看到博文说这是要动态规划的题目,于是我特地想出了不用动态规划的 O(n) 算法。

问题描述:有一串数字,可正可负也可为 0 ,连续两个或多个数字组成了一个子序列,每个子序列都有一个和,求出所有子序列中和最大的一个。例如输入的数组为 3 6 -7 -1 4 3 -2 -5 10 -3 ,则和最大的子序列为 3 6 -7 -1 4 3 -2 -5 10 ,最大和为 11 。

好了,一般情况下,暴力先来:

#include<bits\stdc++.h> 

int n;
int seq[2000];
int ans=-99999999; //因为存在负数 
using namespace std;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&seq[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			int tot=0;
			for(int k=i;k<=j;k++)
			{
				tot+=seq[k];
			} 
			if(tot>ans)ans=tot;
		} 		
	} 
	printf("%d\n",ans);
	return 0;
}

这种解法的复杂度为O(n3),长的数列能把人烦死。

那么就要开始优化了,这要用到一些数学知识,即数列中第 i 项到第 j 项的和,等于 S[j]-s[i-1] ,这里 S 表示多少项的和。

那么我们就要维护一个s数组来记录前面的项数和。

于是优化完了就有了第二种:

#include<bits\stdc++.h> 

int n;
int seq[2002];
int s[2002]; 
int ans=-99999999; //因为存在负数 
using namespace std;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&seq[i]);
		s[i]=s[i-1]+seq[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			int temp=s[j]-s[i-1]; //就是i到j的和啊 
			if(temp>ans)ans=temp;
		} 		
	} 
	printf("%d\n",ans);
	return 0;
}

到这里已经优化到了 O(n2) 了,不过这样还是很慢啊。在这里我们可以用分治把复杂度降到 O(nlogn) ,但是有没有O(n)算法呢。

答案是:有的。

思路很简单,就是呢第二种里的S[j]-s[i-1],这个式子,在j确定的情况下,只要保证s[i-1]最小,就有相减所得最大。

那么我们就要维护一个最小值来记录到此之前的s的最小值。

附上代码:

#include<bits\stdc++.h> 

int n;
int seq[2002];
int s[2002]; 
int smin[2002]; //smin[5]表示下标5以下的s合的最小的那个 
int ans=-99999999; //因为存在负数 
using namespace std;

int main()
{
	s[0]=0;
	smin[0]=0; 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&seq[i]);
		s[i]=s[i-1]+seq[i];
		if(i==1)smin[i]=0;
		else 
		{
			if(s[i-1]<smin[i-1])smin[i]=s[i-1];
			else smin[i]=smin[i-1];
		}
	}
	for(int i=1;i<=n;i++)
	{
			int temp=s[i]-smin[i]; //smin最小时,temp最大 
			if(temp>ans)ans=temp;
	} 
	printf("%d\n",ans);
	return 0;
}

到此为止,算是介绍完了我想到的几种方法。

留下你的评论呗...

电子邮件地址不会被公开。 必填项已用*标注