描述
给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。
例子:
- -
-
- -
- -
其最大子矩阵为: -
-
其元素总和为15。
- 输入
-
第一行输入一个整数n(<n<=),表示有n组测试数据;
每组测试数据:
第一行有两个的整数r,c(<r,c<=),r、c分别代表矩阵的行和列;
随后有r行,每行有c个整数; - 输出
-
输出矩阵的最大子矩阵的元素之和。
- 样例输入
-
- -
-
- -
- - - 样例输出
-
这个问题就是最大值子区间和的二维问题。
最大子区间和是说给你一个数组,然后让你找一个连续的子区间,让这个区间的数的和最大。很经典的简单DP。题目可以参考这个链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=44。
一维问题的解决思路是,max_sum表示从第一数到目前的最大和,sum是某段区间的和,如果sum<0,那么sum没有利用价值了,把sum=0,否则就继续往上加。
max_sum=max((sum+=a[i])<0?0:sum,max_sum);
二维的问题,其实可以转化为一位的问题。
首先我们要注意到二维子矩阵在选取的时候是个矩阵,联系一个我们经常会用到的技巧:但我们需要频繁计算一个数据任意一个区间
的和的时候,我们会预先把这个数组使用啊a[i]=a[i]+a[i-1]的方式把它记录的值变为数组到这个位置的和,这样的好处就是任意一个区间[i,j]的和就可转化为了a[i]-a[j-1]。
在这里我们依然采用这样的技巧。我们把这个矩阵记录的值对于每个列向量都做上述改变。
然后我们就发现,但我们选取任意的连续行进行组合的时候,这个行区间对于的列的值的和都可以用上述方法快速获得,那么对于每个列的和又会变为一个求一维连续区间最大和问题了。到此这个问题就可以以O(n^2)的复杂度解决了。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 106
#define inf 1<<26
int n,m;
int mp[N][N];
int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(mp,,sizeof(mp));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&mp[i][j]);
mp[i][j]+=mp[i-][j];
}
} int MAX = -inf;
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
int tmp = ;
for(int k=;k<=m;k++){
int cnt = mp[j][k]-mp[i-][k];
tmp+=cnt;
if(tmp>MAX) MAX = tmp;
if(tmp<) tmp=;
}
}
}
printf("%d\n",MAX); }
return ;
}