学步园

最大子矩阵和

思想：从i到j （1<=i<=j<=n）行压缩到一维来考虑，要先预处理，设一个数组b[][],b[i][j]表示b[1][j]+b[2][j]+.....+b[i][j],方便求压缩到一维后的数组b[],

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n,matrix[120][120],b[120][120],b1[120],dp[120];
    while(scanf("%d",&n)!=EOF)
	{
       for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
		  {
              scanf("%d",&matrix[i][j]);
		  }
      memset(dp,0,sizeof(dp));
      memset(b,0,sizeof(b));
      int sum=0,ans=0;
      for(int i=1;i<=n;i++)//预处理
         for(int j=1;j<=n;j++)
		 {
             for(int k=1;k<=i;k++)
			 {
                sum+=matrix[k][j];
			 }
             b[i][j]=sum;
             sum=0;
		 }
     for(int i=1;i<=n;i++)
     for(int j=i;j<=n;j++)
	 {
		 for(int k=1;k<=n;k++)
             b1[k]=b[j][k]-b[i][k];
         dp[1]=b1[1];
		 for(int k=2;k<=n;k++)
             if(dp[k-1]>0)
                  dp[k]=dp[k-1]+b1[k];
             else
                  dp[k]=b1[k];
         for(int k=1;k<=n;k++)
              if(ans<dp[k])
                    ans=dp[k];
	 }
     printf("%d\n",ans);
	}
    //system("pause");
    return 0;
}