复杂度是O(n^3)从第一行开始得到以第一行元素为首行的子矩阵的最大和，然后是以第二行为首行的子矩阵的最大和，以此类推，得到最后的最大和。算法实现如下：

/*求数据A的最大子串和*/
int Util::maxsubarray(int* A, int n)
{
 int maxsum = 0;
 int cursum = 0;
 for (int i = 0; i < n ; i++)
 {
  if (cursum <= maxsum)
   cursum += A[i];
  else
   maxsum = cursum;
  
  if (cursum < 0)
   cursum = 0;
 }
 return maxsum;
}

/*求矩阵A的最大子矩阵和*/

int Util::maxsubmatrix(int** A, int n, int m)
{
 int * B = (int *)calloc(m, sizeof(int));
 int maxsum = 0;
 int cursum = 0;
 
 for (int i = 0; i < n; i ++)
 {
  
  memset(B, 0, m);
  
  for ( int j = i; j < n; j ++)
  {
   for (int l = 0; l < m; l++)
    B[l] += A[j][l];
   cursum = maxsubarray(B, m);
   if (cursum > maxsum)
    maxsum = cursum;
  }
 }

 free[] B;
 return maxsum;
}

#include<stdio.h> 
#include<memory.h> 
int n,a[100][100],b[100]; 
int dp1() 
{ 
int sum=0,c=0,max=b[0]; 
for(int i=0;i<n;++i) 
{ 
if(max<b[i])max=b[i]; 
if(c>0)c+=b[i]; 
else c=b[i]; 
if(c>sum)sum=c; 
} 
if(max<0) return max; 
else return sum; 
} 

int dp() 
{ 
int sum=-1000000000; 
for(int i=0;i<n;++i) 
{ 
memset(b,0,sizeof(b)); 
for(int j=i;j<n;++j) 
{ 
for(int k=0;k<n;++k) 
b[k]+=a[j][k]; 
int t=dp1(); 
if(sum<t)sum=t; 
} 
} 
return sum; 
} 
int main() 
{ 
while(scanf("%d",&n)!=-1) 
{ 
for(int i=0;i<n;++i) 
for(int j=0;j<n;++j) 
scanf("%d",&a[i][j]); 
printf("%d\n",dp()); 
} 
return (0); 
}

方法3：
#include<stdio.h> 
#include<memory.h> 
int a[101][100],n,i,max,sum,j,x,k; 
int main() 
{ 
scanf("%d",&n); 
max=-12701; 
for (i=1;i<=n;i++) 
{ 
if (i==1) 
for (j=0;j<n;j++) 
{ 
scanf("%d",&a[1][j]); 
a[0][j]=0; 
} 
else 
for (j=0;j<n;j++) 
{ 
scanf("%d",&x); 
a[i][j]=a[i-1][j]+x; 
} 
} 
for (i=1;i<=n;i++) 
for (j=1;j<=i;j++) 
{ 
sum=0; 
for (k=0;k<n;k++) 
{ 
sum+=(a[i][k]-a[j-1][k]); 
if (sum>max) max=sum; 
if (sum<0) sum=0; 
} 
} 
printf("%d\n",max); 
return 0; 
}