题目链接 Problem - 1081
题意
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
代码语言：javascript复制#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("%dn",ans);
}
return 0;
}方法2
代码语言：javascript复制#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("%dn",ans);
}
return 0;
}
