首页 > 代码库 > 82. 求子序列

82. 求子序列

2024-10-30 21:17:02   210人阅读

★   输入文件：subq.in   输出文件：subq.out   简单对比

时间限制：1 s   内存限制：128 MB

【问题描述】
     给一串整数 a [1… n ] ，求出它和最大的子序列，即找出 1<= i <= j <= n ，使 a [ i ]+ a [ i +1]+…+ a [j-1 ]+ a [ j ] 最大。

【输入格式】 
    文件的第一行为一个正整数n

第二行有n个整数，-32768 ≤ a[i] ≤ 32767

【输出格式】 
   输出文件第一行有一个整数j，表示子序列的起始位置编号。

第二行有一个整数j，表示子序列的终止位置编号。

第三行有一个数，是子序列的和。

注：若有多个解，只输出i值最小的解，若多个解i值相同，则输出j值最小的解。

【输入输出样例】
 
输入： 
subq.in
5
-2 2 5 -1 6

输出：
subq.out
2
5
12

数据范围：

对于30%的数据,n<=100

对于60%的数据,n<=400

对于100%的数据,n<=1,000,000

 

暴力T2：

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N=1050010;int sum[N],a[N],n;inline int read(){	int x=0;int f=1;char c=getchar();	while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}	while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();	return x*f;}int main(){	freopen("subq.in","r",stdin);	freopen("subq.out","w",stdout);	n=read();	for(int i=1;i<=n;i++)		a[i]=read(),		sum[i]=sum[i-1]+a[i];	int maxsum=-(N<<3);	int start,endd;	for(int i=1;i<=n;i++)		for(int j=i;j<=n;j++)			if(sum[j]-sum[i-1]>maxsum)				start=i,				endd=j,				maxsum=sum[j]-sum[i-1];	printf("%d\n%d\n%d\n",start,endd,maxsum);	return 0;}

　　双端队列：

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<deque>using namespace std;	int sum[1000001];int main(){	freopen("subq.in","r",stdin);	freopen("subq.out","w",stdout);	int n;	deque<int> q;		scanf("%d",&n);	for(int i=1;i<=n;i++)	{		scanf("%d",&sum[i]);		sum[i]+=sum[i-1];	}	int s,e;	int dis=-0x7fffffff;	for(int i=1;i<=n;i++)	{ 		while(!q.empty()&&sum[i-1]<=sum[q.back()])			q.pop_back();		q.push_back(i-1);		if(dis<sum[i]-sum[q.front()])		{			dis=sum[i]-sum[q.front()];			s=q.front()+1;			e=i;		}	}	printf("%d\n%d\n%d\n",s,e,dis); 	return 0;}

　　

82. 求子序列


联系
我们