hoj 2558 二维最大子段跟

hoj 2558 二维最大子段和

#include <stdio.h>
#include <cstring>
int a[101][101],sum[101][101];
int f[101];
int main()
{
    int n,t,ans,max;
    while(scanf("%d",&n)==1)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d",&a[i][j]);
        memset(f,0,sizeof(f));
        memset(sum,0,sizeof(sum));
        ans=0,max=-1000000000;
        int temp;
        for(int i=1; i<=n; i++)
        {
            temp=0;
            for(int j=1; j<=n; j++)
                temp+=a[i][j],sum[i][j]=temp;
        }
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++)
            {
                ans=0;
                for(int k=1; k<=n; k++)
                {
                    t=sum[k][j]-sum[k][i-1];
                    if(ans>0) ans+=t;
                    else ans=t;
                    if(ans>max) max=ans;
                }
            }
        printf("%d\n",max);
    }
    return 0;
}