这一题不算难，确定最大值容易，扫描一遍数组即可得，时间复杂度是O(N)，结束的地方也好确定，随着max更新就可以了。最难确定的是开始的界low，为此多花了不少冤枉时间！为了确定low，可以像确定high那样再扫描一遍，不过这次要倒着扫描，从high开始，这两个过程几乎是对称的。
#include<stdio.h>
#define M 100010
#define MIN 10000
int main()
{
int T,i;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
int N,low,high;
long max=-MIN,partsum=0;
int num[M];
scanf("%d",&N);
int j;
for(j=0;j<N;j++)
scanf("%d",&num[j]);
for(j=0;j<N;j++)//正着扫描，确定上界high
{
partsum+=num[j];
if(partsum>max)
{
max=partsum;
high=j;
}
if(partsum<0)
{
partsum=0;
}
}
int partsum2=0,max2=-MIN;//这一遍倒过来扫描，确定下界low
for(j=high;j>=0;j--)
{
partsum2+=num[j];
if(partsum2>=max2)
{
max2=partsum2;
low=j;
}
if(partsum2<0)partsum2=0;
}
if(j==0)low=0;
printf("Case %d:\n",i);
printf("%d %d %d\n",max,low+1,high+1);
if(i!=T)printf("\n");
}
}
花了两个多小时的时间，WA了5次，AC的那一刻实在很爽，相信这也是每个ACMer的原动力所在吧。
posted on 2011-08-19 21:56
小鼠标 阅读(185)
评论(0) 编辑 收藏 引用