Maximum Subsequence Sum

2019-11-06 08:03:48

字体：大中小

来源：转载

供稿：网友

这里写图片描述

题解：该题源于 Maximum Subarray的变种链接如下： http://blog.csdn.net/QQ_27690765/article/details/55805614

代码如下：

#include <iostream>#include<cstdio>const int maxn=100005;int aa[maxn];int main(){ int n; while(scanf("%d",&n)!=EOF) { int PResum=0,sum; int start_=0,end_=0; int flag=0; for(int i=0; i<n; i++) scanf("%d",&aa[i]); sum=aa[0]; /*如果不将n=1单独拿出来，会造成全负值的假象，导致结果出错*/ if(n==1&&aa[0]>=0) printf("%d %d %d/n",sum,aa[0],aa[0]); else { for(int i=0; i<n; i++) { presum+=aa[i]; if(presum>sum) { sum=presum; end_=i; /*标志变量，判断是否更新过end_的值，也就是判断是否是全负值*/ flag=1; } else if(presum<0) presum=0; } presum=0; for(int i=end_; i>=0; i--) { presum+=aa[i]; if(presum==sum) start_=i; } if(!flag&&sum!=0) {///对应于全是负值的情况 sum=0; printf("%d %d %d/n",sum,aa[0],aa[n-1]); } else printf("%d %d %d/n",sum,aa[start_],aa[end_]); } } return 0;}

上一篇：5-7 12-24小时制 (15分)

下一篇：fig3.5