HDU 1003 Max Sum

HDU_1003

最大和的子串是具有这个一个特征的，从左边第一个元素开始逐个累加，每次得到的和一定是大于等于0的，因为如果某一时刻小于0，那么前面一段我们可以抛弃，而后面一段的和一定是大于目前记录的最大和的，这样就矛盾了。

然后我们根据这一特征去寻找最大和的子串即可。

#include<stdio.h>
#include<string.h>
int main()
{
    int i,j,k,N,T,t,ans,x,y,tx,ty,sum;
    scanf("%d",&T);
    for(t=0;t<T;t++)
    {
        scanf("%d",&N);
        ans=-1000000000;
        sum=tx=x=0;
        for(i=0;i<N;i++)
        {
            scanf("%d",&k);
            sum+=k;
            ty=i;
            if(sum>ans)
            {
                ans=sum;
                x=tx;
                y=ty;
            }
            if(sum<0)
            {
                sum=0;
                tx=i+1;
            }
        }
        if(t)
            printf("\n");
        printf("Case %d:\n",t+1);
        printf("%d %d %d\n",ans,x+1,y+1);
    }
    return 0;    
}