这题就是个DP么  一直加 加到和为负数的时候就再从零开始加 中间吧最大值保存下来就OK了啊

呃，理论我已经不想探讨了，只想看一眼AC代码，明白自己死在哪儿就好。

以前写的AC代码：

#include<stdio.h>
int main()
{
    int i,t,n,a[100001],num=0,dp[100001],max,end,begin,q;
    scanf("%d",&t);
    while(t--)
    { 
        num++;
        for(i=0;i<100001;i++) dp[i]=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        max=-99999;begin=1;end=1;q=0;
        for(i=1;i<=n;i++)
        {
            dp[i]+=dp[i-1]+a[i];
            q++;
            if(dp[i]>max)
            {
                max=dp[i];
                end=i;
                begin=i-q+1;
            }
            if(dp[i]<0)
            {   
                dp[i]=0;
                q=0;                
            }
        }
        printf("Case %d:\n",num);
        printf("%d %d %d\n",max,begin,end);
        if(t>0) printf("\n");
    }
    return 0;
}

哦，找时间我会对比一下代码的差别。印象中我的初值用的是串的第一个元素值，动态规划过程只用了一个变量（这倒无所谓），起点终点的计算位置好像不同。

草狼兄弟确定这是AC代码吧？我不拿别人的代码提交我的题目。呵呵，这有点强迫症了。

AC了， 0ms

#include<stdio.h>
int main()
{
    int M, N, i=0, j, s, a[20][3], tmp, t;
    scanf("%d",&M);
    for (; i<M; i++)
    {
        scanf("%d",&N);
        scanf("%d",&s);
        a[i][0]=s, tmp = 0, a[i][1] = 0, a[i][2] = 0;
        for (j=1; j<N; j++)
        {
            scanf("%d",&t);
            s>0?s+=t:(s=t, tmp=j);
            s>a[i][0]?(a[i][0]=s, a[i][1]=tmp, a[i][2]=j):1;
        }
    }
    for (i=0; i<M; i++)
    {
        printf("Case %d:\n",i+1);
        printf("%d %d %d\n",a[i][0],a[i][1]+1, a[i][2]+1);
        i!=M-1?printf("\n"):1;
    }
    return 0;
}

#include<stdio.h>
int main()
{
    int length,temp,i,n,m;
    int max,now,x;
    int begin,end;
    scanf("%d",&n);
    for(m=1;m<=n;m++)
    {
        scanf("%d%d",&length,&temp);
        now = max = temp;
        begin = end = x = 1;
        for(i=2;i<=length;i++)
        {
            scanf("%d",&temp);
            if(now + temp < temp)
                now = temp,x=i;
            else
                now += temp;
            if(now > max)
            {
                max=now;begin=x;end=i;
            }
        }
        printf("Case %d:\n",m);
            printf("%d %d %d\n",max,begin,end);
            if(m!=n) printf("\n");
    }
}
//AC代码弱弱飘过