http://acm.pku.edu.cn/JudgeOnline/problem?id=1050【题目】As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵，如下所示(ari表示a[r][i],假设数组下标从1开始)：
| a11 …… a1i ……a1j ……a1n |
| a21 …… a2i ……a2j ……a2n |
| . . . . . . . |
| . . . . . . . |
| ar1 …… ari ……arj ……arn |
| . . . . . . . |
| . . . . . . . |
| ak1 …… aki ……akj ……akn |
| . . . . . . . |
| an1 …… ani ……anj ……ann |
那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下：
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
由此我们可以看出最后所求的就是此一维数组的最大子断和问题，到此我们已经将问题转化为上面的已经解决了的问题了。
下面是没有优化的代码
PKU 1050
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define maxn 100+5
int n;
int g[maxn][maxn];
int solve()
{
int ans,smax;
int tmp[maxn];
ans=-1270000-100;
for(int l=0;l<n;l++)
for(int r=l;r<n;r++) /*枚举第l列到第r列*/
{
memset(tmp,0,sizeof(tmp));
for(int i=0;i<n;i++)
for(int j=l;j<=r;j++)
tmp[i]+=g[i][j];
smax=tmp[0];
for(int i=1;i<n;i++)
{
if(tmp[i-1]>0) tmp[i]+=tmp[i-1];
if(tmp[i]>smax) smax=tmp[i];
}
if(smax>ans) ans=smax;
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&g[i][j]);
printf("%d\n",solve());
}优化后，少了一层循环。
优化后
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define maxn 100+5
int n;
int g[maxn][maxn];
int solve()
{
int ans,smax,sum;
int tmp[maxn];
ans=-1270000-100;
for(int l=0;l<n;l++)
{
memset(tmp,0,sizeof(tmp));
for(int r=l;r<n;r++) /*枚举第l列到第r列*/
{
for(int i=0;i<n;i++)
tmp[i]+=g[i][r];
smax=sum=tmp[0];
for(int i=1;i<n;i++)
{
if(sum>0) sum+=tmp[i];
else sum=tmp[i];
if(sum>smax) smax=sum;
}
if(smax>ans) ans=smax;
}
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&g[i][j]);
printf("%d\n",solve());
}