首页 > 代码库 > nefu 650 max num
nefu 650 max num
题目:经典dp题目,求出最大相邻子序列的和。
方法:给出两种方法,一种dp,一种直接暴力(数据量小的时候可以考虑)。
代码1:
#include <iostream> #include <cstdio> using namespace std; int main() { int n; int t=1; cin>>n; int s[100010]; while(t<=n) { int m; cin>>m; long long ans=0,sum=0; int l=1,r=1; int p=1,q=1; for(int i=1;i<=m;i++) { cin>>s[i]; sum+=s[i]; if(ans<sum) { ans=sum; p=l;q=r; } if(sum<0) { sum=0; l=i+1; } r++; } if(ans==0) //考虑到全部为负数的情况,则从里面找到一个最大负数即可 { ans=-10001; for(int i=1;i<=m;i++) if(ans<s[i]) { ans=s[i]; p=q=i; } } cout<<"Case "<<t++<<":"<<endl; cout<<ans<<" "<<p<<" "<<q<<endl<<endl; } return 0; }
方法2:
#include<iostream> #include<cstdio> #include <algorithm> using namespace std; struct node { int i1,j1; int sum,ns; }a[10000]; bool cmp(node a,node b) { if(a.sum!=b.sum) return a.sum>b.sum; else return a.ns<b.ns; } int main() { int n,b[100000]; while(scanf("%d",&n)!=EOF) { int ans=1; while(n--) { int m,i,j,k,q; scanf("%d",&m); for(i=0;i<m;i++) scanf("%d",&b[i]); for(i=0,k=0;i<m;i++) for(j=i;j<m;j++) { a[k].sum=0;a[k].ns=k; a[k].i1=i+1;a[k].j1=j+1; for(q=i;q<=j;q++) a[k].sum+=b[q]; k++; } sort(a,a+k,cmp); printf("Case %d:\n",ans++); printf("%d %d %d\n\n",a[0].sum,a[0].i1,a[0].j1); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。