学步园

求最大子段和，每次记录当前子段和，和当前子段的开始位置，更新最大子段和，如果当前子段和小于0，则重新开始计算子段和（因为子段加一个负数值会更小）。

代码：

//最大子段和
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#define INF 0x7fffffff
#define maxn 0x7fffffff
#define maxl 0x7fffffff
#define fi for(int i=0;i<n;i++)
#define fj for(int j=0;j<n;j++)
#define wh while(t--)
using namespace std;
int main()
{
    int n,a;
    int t;
    scanf("%d",&t);
    for(int tt=1; tt<=t; tt++)
    {
        scanf("%d",&n);
        int Max=-INF;//Max为最大子段和，tempt表示当前子段和
        int tempt=0;
        int s=1;
        int e=1;
        int k=1;//当前段的开始位置
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a);
            tempt+=a;
            if(tempt>=Max)
            {
                Max=tempt;
                s=k;
                e=i;
            }
            if(tempt<0)
            {
                tempt=0;
                k=i+1;
            }
        }
        if(tt!=1)
        printf("\n");
        printf("Case %d:\n",tt);
        printf("%d %d %d\n",Max,s,e);
    }
    return 0;
}