果的最大子矩阵问题，用到了最大子区间
#include <stdio.h>
#include <string.h>
int num[200][200];
int sub[200][200];
int n;
int maxnum(int *p)
{
int max=0, sum=0;
for ( int i = 1; i < n; i++ )
{
sum+=p[i];
if ( sum < 0) sum= 0;
else if ( sum > max) max= sum;
}
return max;
}
int max()
{
int t[200];
int i, j, k, m=0, l;
for ( i = 1; i <= n; i++ )
for ( j = i; j <= n; j++ )
{
for ( k = 1; k <= n; k++ )
t[k]=sub[j][k]+sub[i-1][k-1]-sub[j][k-1]-sub[i-1][k];
l=maxnum(t);
if (l > m) m=l;
}
return m;
}
int main()
{
while ( EOF != scanf("%d", &n) )
{
int i, j;
for ( i = 1; i <= n ; i++ )
for ( j = 1 ; j <= n ; j++ )
scanf("%d", num[i]+j);
memset(sub, 0, sizeof(sub));
sub[1][1]=num[1][1];
for ( i = 1; i <= n ; i++ )
for ( j = 1; j <= n ; j++ )
sub[i][j]=sub[i-1][j]+sub[i][j-1]+num[i][j]-sub[i-1][j-1];
printf("%d\n", max());
}
return 0;
}