杭电OJ1003--最大和问题

本题巧用结构体，记录分别以a[0],a[1]....为结束位置的最大子串，以达到遍历所有最大子串的效果，b[].x为该子串的起始位置，b[].lar为该子串的和。最后找出以a[i]为终点的子串为最大子串，记录他的起始位置x，和终点i.
#include <stdio.h>
#include <stdlib.h>
struct{
int x;
int lar;
}b[100000];
int main()
{
    int i,t,n,a[100000],m,max,s,k;
    scanf("%d",&t);//执行次数
    m=t;记录原始执行次数便于printf("Case %d:\n",m-t);
    while(t--)
    {
        scanf("%d",&n);//每一组数的个数
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }//输入每一组数
        b[0].x=0;//以a[0]为终点的最大子串的起始位置
        b[0].lar=a[0];//以a[0]为终点的最大子串的和
        for(i=1;i<n;i++)
        {
            if((b[i-1].lar+a[i])<a[i])
            {
                b[i].lar=a[i];
                b[i].x=i;
            }
            else
            {
                b[i].lar=b[i-1].lar+a[i];
                b[i].x=b[i-1].x;
            }
        }//找出分别以a[0],a[1]....为结束位置的最大子串及其起始位置
         max=-1000;//每次找出所有最大子串中的最最大时，不要忘记赋初始值，不然执行第二组数据时会报错。
        for(i=0;i<n;i++)
        {
            if(max<b[i].lar)
            {
                max=b[i].lar;
                s=b[i].x;
                k=i;
            }
        }
        printf("Case %d:\n",m-t);
        printf("%d %d %d\n",max,s+1,k+1);
        if(t!=0)printf("\n");//注意最后一组数据无需空行。
    }
}