#include<stdio.h>
#include<malloc.h>
int main()
{
	int n,i,j,g,k,b2,s,ma[101][101],* b;
	scanf("%d",&n);
	for(j=1;j<=n;j++)
		for(i=1;i<=n;i++)
			scanf("%d",&ma[j][i]);
	b=(int *)malloc(sizeof(int)*(n+1));
	s=-10000;
	for(k=1;k<=n;k++){
		for(g=k;g<=n;g++){//k->g column枚举每种列的情况
			for(j=1;j<=n;j++){
				b[j]=0;
				for(i=k;i<=g;i++)
					b[j]+=ma[j][i];
			}	
			b2=0;
			for(j=1;j<=n;j++){//一维数组的DP步骤
				if(b2>0)
					b2+=b[j];
				else
					b2=b[j];
				if(b2>s)
					s=b2;
			}
		}
	}
	printf("%d",s);
	return 0;
}

• Re:大哥，你这算法n^3的好不？ (618) yzhw 2009-02-13 09:59:55