学步园

//http://acm.hdu.edu.cn/showproblem.php?pid=1003
#include<stdio.h>
int main()
{
    int a[100001],max,sum,n,t,flag,flag1,flag2,i,m=0;
    while(scanf("%d",&t)!=EOF)
    {
        while(t--)
        {
            scanf("%d",&n);
            max=-999999;sum=0;flag=1;
            for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                sum+=a[i];
                if(sum>max)
                {
                   max=sum;
                   flag1=flag;
                   flag2=i;
                }
                if(sum<0)
                {
                    sum=0;
                    flag=i+1;
                }
            }
            printf("Case %d\n",m++);
            printf("%d %d %d\n",max,flag1,flag2);
            if(t!=0)
              printf("\n");
        }
    }
    return 0;
}
/*
这主要是DP里面的算法，有几点需要注意的
1：sum和max是至关重要的，其中sum主要是求前几个元素的和，而max则是作为控制的条件
其中的值就是我们所求的最大的答案，也是保存着大于0的和
2：flag2代表着我们所加大的最大元素之和的最后一个i值，当sum小于0的时候，flag的值要+1，因为这时候sum的
值已经清零了，我们也要从下一个数字开始加，而flag1 则是时刻和flag的值变化而变化，这里要明白，flag的值要
提前定义一个值，也只能是1，谁叫是从1开始
3：数据大小问题，a的数组一定要超w，开始写的时候，只有一千多，一直都是WA，改成W就AC了
4：主要格式问题，题目要求，最后一个后面不需要再输入换行了，后面一个对t判断就很关键了，别到时候又是无限次PE
例如 6 -1 5 4 -7 这几个元素
首先可以得到max=sum=6，再运行一遍sum就成了5，但是此时max还是6，别急，运行到下一次，sum>max了，这两个if
就是很关键的条件，这样就达到了我们所需的结果了
*/