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());
}