1051 最大子矩阵和

题目链接：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1051

题解：

一道很好的思维题，主要是将二维的数组压缩称为一维的数组，然后就按常规的做法就行了。（这里有一个坑点，这里的输入的时候，是m在前，n在后的。）

代码：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define met(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f const int maxn = 500+10; int mp[maxn][maxn]; int dp[maxn][maxn]; int main() { int n,m; while(scanf("%d%d",&m,&n)!=EOF) { met(mp,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int num; scanf("%d",&num); mp[i][j]=mp[i-1][j]+num; } // 将二维的压缩称为一维的。 int sum=0; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) // 枚举一维数组，类似于线段树的思想。 { int ans=0; for(int k=1;k<=m;k++) { ans+=mp[j][k]-mp[i-1][k]; if(ans<0) ans=0; else sum=max(ans,sum); } } printf("%d\n",max(sum,0)); } }