菜鸟请教广工一道OJ题

这是题目内容：

下面是我自己写的代码，但提交后是超时（Time Limit Exceeded），请教大神有什么更优的解法吗

#include<stdio.h>

int main()
{
    int T,n,i,a[10003],t,sum,max;

    scanf(“%d”,&T);

    while(T–)
    {
        sum=0;

        scanf(“%d”,&n);

        for(i=1; i<=n; i++)
        {
            scanf(“%d”,&a[i]);
        }

        for(t=2; t<=n; t++)
            sum=sum-a[t];

        if(sum<0)
            sum=-sum;

        max=sum;

        for(i=2; i<=n; i++)
        {
            sum=0;

            for(t=1; t<=n; t++)
            {
                if(t>i)
                    sum=sum-a[t];
                else if(t<i)
                    sum=sum+a[t];
            }

            if(sum<0)
                sum=-sum;

            if(sum>max)
                max=sum;

        }

        printf(“%d\n”,max);
    }

    return 0;
}