杭电1003.cpp

这是杭州电子科技大学acm网的一道题1003

/*算法：1.一直相加直到和出现负数，在相加期间能得到一个最大和，记录
2.重复1步骤，更新最大和，直到输入完毕
原理：如果在连续子串 <a1,a2,a3,...,an> 中Sn<0;S1,S2,...S(n-1)均大于或等于0
那么肯定存在一个最大的Si,Si也就是a1到an这段连续子串的最大和。
我们知道a1>0时任意的 <ai...an> (i>1) 的和都小于0，
所以这些元素就不能与an后的元素构成能获得最大和的子串(如果a1=0则a2>=0,情况类似);
同时在 <ai...aj> (i>1,j<=n) 也不能或得比Si大的和。*/
#include<stdio.h>
int i,cas,j,k,t,max,s,e,n,x;
int main()
{
    while(scanf("%d",&cas)!=EOF)
    {
        for(i=0;i<cas;i++)
        {
            if(i)printf("\n");
            printf("Case %d:\n",i+1);
            scanf("%d",&n);
            max=-9999;
            for(j=k=1,t=0;j<=n;j++)
            {
                scanf("%d",&x);
                t+=x;
                if(t>max) {max=t;s=k;e=j;}
                if(t<0)      {k=j+1;t=0;}
            }
            printf("%d %d %d\n",max,s,e);
        }
    }
return 0;
}