Question

杭电ACM1003感觉自己测试数据都是对的，怎么还是wrong answer

#include<iostream>
using namespace std;
int main()
{
int t,num[100001],i,k,max,sum,start,end,n;
cin>>t;
for(k=1;k<=t;k++)
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>num[i];
}
max=-1001;
start=1;
end=1;
sum=0;
for(i=1;i<=n;i++)
{
sum=sum+num[i];
if(sum>max)
{
max=sum;
end=i;
}
if(num[i]>max)
{
max=num[i];
start=i;
end=i;
sum=max;
}
}
cout<<"Case "<<k<<':'<<endl;
cout<<max<<' '<<start<<' '<<end<<endl;
cout<<endl;
}
return 0;
}

Answer 1

代码明显错了 你的数据也太弱了吧 给你一组 1 2 1答案是4 1 3按照你的程序是2 2 2吧
我的代码你可以参考下，你程序下面应该判断sum小于0的情况
#include<iostream>
using namespace std;
int main()
{
int cas,i;cin>>cas;
for(i=1;i<=cas;i++)
{
int n,j,sum=0,max=-1001,start=1,end=1,x,f=1;
cin>>n;
for(j=1;j<=n;j++)
{
cin>>x;
sum+=x;
// cout<<"start: "<<start;
if(sum>max)
{max=sum;start=f;end=j;}
if(sum<0)
{sum=0;f=j+1;}
//cout<<"f: "<<f;

}
printf("Case %d:\n",i);
printf("%d %d %d\n",max,start,end);
if(i!=cas)
putchar('\n');

}
return 0;
}

Answer 2

#include<iostream>
using namespace std;
int main()
{
	int t, num[100001], i, k, max, sum, start, end, n;
	int tempstart;
	cin >> t;
	for (k = 1; k <= t; k++)
	{
		if (k != 1) {
			cout << endl;
		}
		cin >> n;
		for (i = 1; i <= n; i++)
		{
			cin >> num[i];
		}
		max = num[1];
		start = 1;
		tempstart = 1;
		end = 1;
		sum = 0;
		for (i = 1; i <= n; i++)
		{
			if (sum >= 0)
				sum = sum + num[i];
			else {
				sum = num[i];
				tempstart = i;
			}
			if (sum>max)
			{
				max = sum;
				start = tempstart;
				end = i;
			}
		}
		cout << "Case " << k << ':' << endl;
		cout << max << ' ' << start << ' ' << end << endl;
	}
	return 0;
}

追问

中间这段代码大概是什么意思？从23行开始。谢谢！我当初的想法是比较两种情况，如果当前的sum大于max,就将i赋给end编号，如果此时这个num[i]本身就大于max的话，那么就将start,end都赋此时的i值（例如：4，-100,6，-1那么当加到6时虽然sum小于max，但是6大于4（此时最大值），所以将start，end赋3）。为什么是不对的？

追答

1
3 4 -5 6

试一下就知道了

追问

也是对的，其实就是不知道为什么自己的编写的代码还是有问题？

追答

我刚刚搞错测试数据了

你再试试

1
4 4 -5 3 3