Question

杭电ACM1003 Max Sum C语言求那里错了

#include <stdio.h>
int main()
{
int a[100001]={0},i[3],b,n,sum;
while(scanf("%d",&i[0])==1)
{
for(i[1]=1;i[1]<=i[0];i[1]++)
{
sum=0;
scanf("%d",&i[2]);
for(b=1;b<=i[2];b++)
scanf("%d",&a[b]);
for(b=1;b<=i[2];b++)
if(a[b]>=0) break;
n=b;
while(n<=i[2])
{
if(a[n]>=0)
sum=sum+a[n];
else if(a[n+1]>=(-a[n]))
{
if((-a[n])>sum)
{sum=0;b=n+1;}
else sum=sum+a[n];
}
else
break;
n++;
}
printf("Case %d:\n",i[1]);
printf("%d %d %d\n",sum,b,n-1);
if(i[1]<i[0])
printf("\n");

}

}

return 0;

}

Answer 1

这是经典的“最长连续子序列”问题，只是对于全部数字为负数的处理与传统问题略有不同，这里提供一个O(n)算法的AC代码：

#include <stdio.h>
int main(){
    int a,t,n,i,j,k,l,u,max,s;
    scanf("%d",&t);
    for(k=1;k<=t;k++){
        if(k-1) printf("\n");
        scanf("%d",&n);
        max=-1001;
        for(i=j=1,s=0;j<=n;j++){
            scanf("%d",&a);
            s+=a;
            if(s>max){max=s;l=i;u=j;}
            if(s<0){i=j+1;s=0;}
        }
        printf("Case %d:\n%d %d %d\n",k,max,l,u);
    }
    return 0;
}

 另外杭电ACM中problem-1231有一个类似的问题，你不妨也看看。

追问

能帮我看看我的那里错了吗？

追答

首先a[100001]完全没必要；你的程序命名让人不太明白，你最好先解释下自己的思路，给个大致的伪码说明，也好理解你的代码要做什么。

追问

好吧。其实我也看不懂我写的是什么了