首页 > 代码库 > 82. 求子序列
82. 求子序列
★ 输入文件: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. 求子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。