【 HDU1081 】 To The Max （最大子矩阵和）
题意
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
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. 求最大的子矩阵和。
题解
这题注意要多组输入输出。
方法1
方法2
看了别人的，突然觉得自己的真麻烦。 s[i][j]表示第i行的前j列的和。 枚举左右边界的列编号i,j，sum保存第i列到第j列从第k行往上连续的最大和。这个过程只需枚举k从1到n，只要之前的sum是正的就继续累加，否则sum=0再加：sum+=s[k][j]-s[k][i-1]。用sum更新ans即可。
代码
方法1
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 105
using namespace std;
int n,a[N][N],g[N][N],s[N][N],ans;
int main() {
while(~scanf("%d",&n)){
ans=-127;
memset(g,0,sizeof g);
memset(s,0,sizeof s);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int k=1;k<=n;k++)
for(int l=1;l<=n;l++){
s[k][l]=s[k-1][l]+s[k][l-1]-s[k-1][l-1]+a[k][l];
for(int i=0;i<k;i++){
int &j=g[k][i];
ans=max(ans,s[k][l]-s[i][l]-s[k][j]+s[i][j]);
if(s[k][j]-s[i][j]>s[k][l]-s[i][l])j=l;
}
}
printf("%d\n",ans);
}
return 0;
}方法2
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 105
using namespace std;
int n,s[N][N],ans,sum;
int main() {
while(~scanf("%d",&n)){
memset(s,0,sizeof s);
ans=-127;sum=0;
for(int i=1,a;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&a);
s[i][j]=s[i][j-1]+a;
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=1;k<=n;k++){
if(k==1||sum<0)sum=0;
sum+=s[k][j]-s[k][i-1];
ans=max(ans,sum);
}
printf("%d\n",ans);
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-02-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
