首页 > 代码库 > PAT甲题题解-1007. Maximum Subsequence Sum (25)-求最大子区间和
PAT甲题题解-1007. Maximum Subsequence Sum (25)-求最大子区间和
题意:给出n个数,求最大连续的子区间和,并且输出该区间的第一个和最后一个数。
如果所有数都小于0,那么则输出0,第一个数和最后一个数。
看数据k的范围,就知道肯定不能两层for循环来求区间和,O(n^2)的复杂度肯定超时
所以这里肯定要求一遍for循环就能知道结果
定义区间l和r,sum为目前[l,r]之间的和
一开始l=r=0,sum=a[0]
接下来,对于当前第i个数字a[i]
如果sum+a[i]>a[i],那么就将a[i]一起加入到区间中去。
如果sum+a[i]<a[i],那么还不如不加,直接重新从a[i]开始,sum=a[i]。
更新对应的区间,顺便比较一下当前的sum和maxsum即可
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string.h> #define INF 0x3f3f3f3f using namespace std; const int maxn=10000+5; int a[maxn]; int maxsum=-INF; int maxl,maxr; int l,r; int main() { int n,val; int sum; scanf("%d",&n); scanf("%d",&a[0]); sum=a[0]; l=0; r=0; maxl=l; maxr=r; maxsum=sum; bool allnegative=true; if(a[0]>=0) allnegative=false; for(int i=1;i<n;i++){ scanf("%d",&a[i]); if(a[i]>=0) allnegative=false; //printf("l:%d r:%d sum:%d %d:val\n",l,r,sum,a[i]); if(sum+a[i]>a[i]){ sum+=a[i]; r++; if(sum>maxsum){ maxl=l; maxr=r; maxsum=sum; } } else{ sum=a[i]; l=r=i; if(sum>maxsum){ maxl=l; maxr=r; maxsum=sum; } } } //如果都小于0,按照题目要求,输出0,第一个和最后一个数 if(allnegative) printf("0 %d %d\n",a[0],a[n-1]); else printf("%d %d %d",maxsum,a[maxl],a[maxr]); return 0; }
PAT甲题题解-1007. Maximum Subsequence Sum (25)-求最大子区间和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。