学步园

 这题是一道经典的DP问题，将求最大子矩阵和转化为求数组的最大子序列的和，由于不需要给出得到最大值时子矩阵的位置，所以可以用o(n)的那个算法来求数组的最大子序列，我的代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUM 109
short arr[MAX_NUM][MAX_NUM];
short tmp[MAX_NUM];
int n;

int get_max(){
 int max_s=0,tmp_s=0;
 for(int i=0;i<n;i++){
  tmp_s+=tmp[i];
  if(tmp_s>max_s)
   max_s=tmp_s;
  if(tmp_s<0)
   tmp_s=0;
 }
 return max_s;
}

int main(){
 //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

 while (EOF != scanf ("%d", &n))
    {
         for (int i = 0; i < n; ++i)
         {
             for (int j = 0; j < n; ++j)
             {
                 scanf ("%d", &arr[i][j]);
             }
         }
 
 int max_sum=0;
 int row=0,ctr,tmp_sum;
 while(row<n){
  for(ctr=row;ctr<n;ctr++){
   memset(tmp,0,sizeof(tmp));
   for(int i=0;i<n;i++){   //算出一次tmp数组
    for(int j=row;j<=ctr;j++){
     tmp[i]+=arr[i][j];
    }
   }
   tmp_sum=get_max();
   if(tmp_sum>max_sum)
    max_sum=tmp_sum; 
  }
  row++;
 }
 printf ("%d\n", max_sum);
 }

    return 0;
}