1050.cpp

流牛木马原创POJ解题报告集１ http://www.cppblog.com/aclayton

#include <stdio.h>
int a[102][102]={0};
int maxsum(int a[],int n)
{
    int i,sum=0,b;
    b=a[0];
    for(i=1;i<=n;i++)
    {
       if(b>0)b+=a[i];
        else b=a[i];
        if(b>sum)sum=b;
        }
        return sum;
}

int maxsum2(int n)
{
    int i,j,k,sum=0,max; 
    int b[102]={0};
    for(i=0;i<=n;i++)
    {
        for(k=0;k<=n;k++)b[k]=a[i][k];
        for(j=i+1;j<=n;j++)
        {
            for(k=0;k<=n;k++)b[k]+=a[j][k];
            max=maxsum(b,n);
            if(max>sum)sum=max; 
        }
    }
    return sum;
}
    
int main()
{
    int i,j,N;
    while(scanf("%d",&N)!=EOF)
    {
        for(i=0;i<=N-1;i++)
        for(j=0;j<=N-1;j++)
        scanf("%d",&a[i][j]);
        printf("%d\n",maxsum2(N-1));
    }
    return 0;
}