Question

关于杭电acm 为什么提交上去老提示 wrong answer 求高手解答

#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[100005],sum[100005];
int n,i=1,num,j,begin=1,end=1,max;
scanf("%d",&n);
if(n>20||n<0)
printf("error\n");
while(n--)
{
scanf("%d",&num);
for(j=1;j<=num;j++)
{
scanf("%d",&a[j]);
if(a[j]>1000||a[j]<-1000)
printf("error!");
}

max=sum[1]=a[1];
for(j=2;j<=num;j++)
{
if(sum[j-1]<0)
{
sum[j]=a[j];
begin=j;
if(max<sum[j])
{
max=sum[j];
end=j;
}
}
else
{
sum[j]=sum[j-1]+a[j];
if(sum[j]>max)
{
max=sum[j];
end=j;
}
}
}
printf("Case %d\n",i);
printf("%d %d %d\n",max,begin,end);
if(i<=n)
printf("\n");
}
return 0;
}

Answer 1

#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[100005],sum[100005];
int n,i=1,num,j,begin=1,end=1,max,temp;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&num);
for(j=1;j<=num;j++)
{
scanf("%d",&a[j]);
}

max=sum[1]=a[1];
temp = 1;
begin = end = 1;
for(j=2;j<=num;j++)
{
if(sum[j-1]<0)
{
sum[j]=a[j];
temp=j;
}
else
{
sum[j]=sum[j-1]+a[j];
}
if(max<sum[j])
{
begin = temp;
max=sum[j];
end=j;
}
}
printf("Case %d:\n",i);
printf("%d %d %d\n",max,begin,end);
if(i<n)
printf("\n");
}
return 0;
}

追问

请问 temp在这里起到什么作用，我测试了几组数据都没有问题？麻烦了，thx

追答

temp的作用是记录临时的起点，只有在max<sum[j]的情况下才需要把begin更新为temp的值
参考下面的Case
1
3 3 -4 2