UC知道hdu 1003 大家看一下我这个程序有什么漏洞 总是过不了
来源：百度知道 编辑：UC知道 时间：2024/05/25 18:05:36
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
int main()
{
int T,i,n[20];
int a[20][10000];
int j,sum=0,max[20],end[20],begin,start[20];
cin>>T;
for(i=0;i<T;i++)
{
cin>>n[i];
max[i]=-1000;
for(j=0;j<n[i];j++)
cin>>a[i][j];
}
j=0;
for(i=0;i<T;i++)
{
max[i]=sum=a[i][0];
begin=1;
start[i]=1;
end[i]=1;
for(j=1;j<n[i];j++)
{
if(a[i][j]<0&&sum+a[i][j]<0)//判断负数，且下一个数的和为负数时
{
if(max[i]<sum)
{max[i]=sum;start[i]=begin;end[i]=j+1;}
sum=0;
while(a[i][j]<0&&j<n[i])++j;
begin=j+1;
}
sum+=a[i][j];
if(max[i]<sum)
{
max[i]=sum;
start[i]=begin;
end[i]=j+1;
}
}
}
for(i=0;i<T;i++)
{
if(i) cout<<endl;
using std::cout;
using std::cin;
using std::endl;
int main()
{
int T,i,n[20];
int a[20][10000];
int j,sum=0,max[20],end[20],begin,start[20];
cin>>T;
for(i=0;i<T;i++)
{
cin>>n[i];
max[i]=-1000;
for(j=0;j<n[i];j++)
cin>>a[i][j];
}
j=0;
for(i=0;i<T;i++)
{
max[i]=sum=a[i][0];
begin=1;
start[i]=1;
end[i]=1;
for(j=1;j<n[i];j++)
{
if(a[i][j]<0&&sum+a[i][j]<0)//判断负数，且下一个数的和为负数时
{
if(max[i]<sum)
{max[i]=sum;start[i]=begin;end[i]=j+1;}
sum=0;
while(a[i][j]<0&&j<n[i])++j;
begin=j+1;
}
sum+=a[i][j];
if(max[i]<sum)
{
max[i]=sum;
start[i]=begin;
end[i]=j+1;
}
}
}
for(i=0;i<T;i++)
{
if(i) cout<<endl;
这道题我也是WA了好几次。发现一个规律。得把范围放得尽量大。有些时候两个范围产生的最大值是一样的。这个时候就得选最大的一个范围。顺便附上我的代码：
#include<stdio.h>
void main()
{
int n,t;
long num,pre_sum,now_sum,i,to,from,from1,counter=0;
scanf("%d",&n);
while(n--)
{
pre_sum=-1000000000;
now_sum=0;
from1=1;
scanf("%ld",&num);
for(i=1;i<=num;i++)
{
scanf("%d",&t);
now_sum+=t;
if(now_sum>pre_sum)
{
pre_sum=now_sum;
from=from1;
to=i;
}
if(now_sum<0)
{
now_sum=0;
from1=i+1;
}
}
printf("Case %d:\n%d %d %d\n",++counter,pre_sum,from,to);
if(n!=0)
p