题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
---|---|---|---|---|---|
Max Sum | ★☆☆☆☆ | 答案正确 | 100 | 2015-02-06 10:58:51 | 无 |
给一串序列,求子序列使得其和最大。
即记=a[1]+a[2]+...+a[i],那么
1003.cpp代码已折叠
展开折叠内容
|
---|
#include<cstdio> #include<cstring> #include<climits> #define _for(i,n) for(int i=1;i<=n;++i) int sum[120000]={},a[120000]={}; void Work() { sum[0]=0; int n,ans=INT_MIN,ansX,ansY,sumMin=0,sumMinN=0; scanf("%d",&n); _for(i,n) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; if(sum[i]-sumMin>ans) { ans=sum[i]-sumMin; ansX=sumMinN+1; ansY=i; } if(sumMin>sum[i]) { sumMin=sum[i]; sumMinN=i; } } printf("%d %d %d\n",ans,ansX,ansY); } int main() { int T; scanf("%d",&T); _for(i,T) { printf("Case %d:\n",i); Work(); if(i!=T) printf("\n"); } } |