Question

[求教]杭电ACM 1003题 MAX SUM

#include<stdio.h>
int main()
{int n,a[100000],i,j,t,k,nn,lef,rig,max,sum;

scanf("%d",&n);
for(nn=1;nn<=n;nn++)
{ t=0;
scanf("%d",&t);
for(i=0;i<t;i++)
a[i]=0;

for(j=0;j<t;j++)
scanf("%d",&a[j]);
max=0;sum=0;rig=0;lef=0;
for(k=0;k<t;k++)
{ sum+=a[k];
if(sum>max) {max=sum;rig=k+1;}
}
sum=0;max=0;
for(k=rig-1;k>=0;k--)
{sum+=a[k]; if(sum>=max) {max=sum;lef=k+1;}
}

printf("Case %d:\n",nn);
printf("%d %d %d",max,lef,rig);
if(nn!=n) printf("\n\n");

}

return 0;
}

不知道错在哪 请高手指点 感激不尽
http://acm.hdu.edu.cn/showproblem.php?pid=1003

Answer 1

我也想了半天才想明白……你的核心算法有问题
我们举例说明
-1 -3 2 -4 -5
按题目要求应该输出 2 3 3 对吧
但是你的程序根本找不到lef和rig，因为从左往右没有某个和大于0
然后，我把两处max=0修改为max=-2147483648提交，仍然是WA，应该是还有别的问题
比如，-2 -4 -5 -1 -4这个数列，题目的输出应该是-1 4 4 但是显然这个程序无法处理全是负数的数列，故应将此情况单独考虑。
解决方案：另外定义flag，读入a[j]前令flag=0，一旦读到一个正数令flag=1.到了下面，如果flag=1则正常执行你写的这部分程序，如果flag=0执行另一段单独考虑负数的程序即可。

另外，看你好像是ACM初学，建议你看一下算法导论的第一章，里面有这道题的四种算法，写的很好
http://wenku.baidu.com/view/1e1b401ca300a6c30c229f76.html

Answer 2

想实现什么功能

Answer 3

int 最多能定义65535 a[100000]太大了~~