本文共 764 字,大约阅读时间需要 2 分钟。
突破口:把握好sum<0的意义
#include#include using namespace std;int a[100005];int main(){ int T,n,i,kase; int max,sum,start,end,st,et; //max作为最终输出的答案,sum作为游标,去探测 scanf("%d",&T); kase=1; while(T--) { sum=0; scanf("%d",&n); for(i=0;i<=n-1;i++) scanf("%d",&a[i]); for(i=0;i<=n-1;i++) { if(i==0) { start=end=st=et=0; max=sum=a[0]; } else { sum+=a[i]; et=i; } if(sum<0) //sum<0,起点要重新设置 { if(sum>=max) //只有sum>=max时,才将sum的值赋给max,并记录下起点与重点 { max=sum; start=st; end=et; } sum=0; st=et=i+1; //起点重新设置 } else { if(sum>=max) { max=sum; start=st; end=et; } } } printf("Case %d:\n",kase++); printf("%d %d %d\n",max,start+1,end+1); if(T!=0) printf("\n"); } return 0; }
转载地址:http://efdci.baihongyu.com/