Question

杭电1003求解题思路！！

http://acm.hdu.edu.cn/showproblem.php?pid=1003
#include<stdio.h>
#include<stdlib.h>
int main()
{
int t,num,count;
long sum,max,n,i,start, end, a;

scanf("%d",&t);
for ( count=1; count <= t; count++ )
{
sum = 0;
max = -999999999;
start = a = 1;
end = 0;
scanf("%ld",&n);

for (i=1; i <= n; i++)
{ scanf("%d",&num);
sum += num;
if (sum > max)
{
max = sum;
start = a;
end = i;
}
if (sum < 0)
{
sum = 0;
if (num < 0)
a = i+1;
else
a = i;
}
}
printf("case:%d\n",count);
printf("%ld %d %d\n",max,start,end);
if (count != t)
printf("\n");
}

system("pause");
return 0;
}

Answer 1

//#include "StdAfx.h"
#include<iostream>
using namespace std;
int main()
{
int zu;
cin>>zu;
for(int j=1;j<=zu;j++)
{
if(j!=1)
cout<<endl;
int nums,c,sum=0,start=0,end=nums-1,temp=0,max=-99999999;
cin>>nums;
for(int i=0;i<nums;i++)
{
cin>>c;
sum+=c;
if(sum>=max)
{
start=temp;
end=i;
max=sum;
}
if(sum<0)
{
sum=0;
if(c>=0)
temp=i;
else
temp=i+1;
}
}
cout<<"Case "<<j<<":"<<endl;
cout<<max<<" "<<start+1<<" "<<end+1<<endl;
}
}
可以一边输入，一边判断处理。temp表示起点位置，start表示sum最大时的开始位置，end表示sum最大时的结束为止。end可以跟随i前进故不用在定义一个临时变量。当sum>=max时 ，更新数据 当sum<0 是更新开始位置。

追问

你的思路我看懂了，我自己照着编了一个，可是还是不通过，不知怎么回事，能帮忙看看吗？

追答

我们都一样，其实刚开始接触新的思路记住它蛮难的，但以后类似的题目做多了自然而然间就能条件反射了。
printf("case:%d\n",count); // 输出格式错了,改成printf("Case %d:\n",count);就能AC了。

追问

系统给出的是答案错，这不是输出格式错，刚才我改了，还是错的，说明不是格式的问题，晕了，想不通为什么错。。

追答

我刚交过了 AC

追问

为什么我的程序就是错的呢？奇怪了。。。if (sum > max)改成if (sum >= max)
也是错的，不知所以然，求助~！

Answer 2

声明个数组int a[20][10000] 不过感觉这样子 是不是时间要求会不过~

追问

穷举会超时

追答

没打算穷举 你可以来个count　来计算你输入了多少个数字　不是？
第一个数字　不就是多少个case吗　到时候　两个for循环　不会循环20次跟10000次

追问

具体的怎么算，感觉这样 会超时的，我贴我的代码，你看看，超时了

追答

scanf("%d",&n);
for ( i=0; i < n; i++ )
为什么这里循环是n？