最大子矩阵和问题归纳总结

本文主要是介绍最大子矩阵和问题归纳总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一，最大子矩阵问题：
给定一个n*n(0< n <=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。
Example：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其中左上角的子矩阵：
9 2
-4 1
-1 8
此子矩阵的值为9+2+(-4)+1+(-1)+8=15。

二，分析
子矩阵是在矩阵选取部份行、列所组成的新矩阵。
我们首先想到的方法就是穷举一个矩阵的所有子矩阵，然而一个n*n的矩阵的子矩阵的个数当n比较大时时一个很大的数字 O(n^2*n^2)，显然此方法不可行。怎么使得问题的复杂度降低呢？对了，相信大家应该知道了，用动态规划。对于此题，怎么使用动态规划呢？

    请先参考-->最大子段和问题这个问题与最大子段有什么联系呢？

1、首先考虑一维的最大子段和问题，给出一个序列a[0]，a[1]，a[2]…a[n]，求出连续的一段，使其总和最大。

a[i]表示第i个元素
dp[i]表示以a[i]结尾的最大子段和

dp[i] = max{a[i], dp[i-1] + a[i]}

解释一下方程:

如果dp[i-1] > 0，则 dp[i] = dp[i-1] + a[i]
如果dp[i-1] < 0，则 dp[i] = a[i]

因为不用记录位置信息，所以dp[]可以用一个变量dp代替:

如果dp > 0，则dp += a[i]
如果dp < 0，则dp = a[i]

2、考虑二维的最大子矩阵问题

我们可以利用矩阵压缩把二维的问题转化为一维的最大子段和问题。因为是矩阵和，所以我们可以把这个矩形的高压缩成1，用加法就行了。

假设最大子矩阵的结果为从第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)
由此我们可以看出最后所求的就是此一维数组的最大子段和问题，到此我们已经将问题转化为上面的已经解决了的问题了。

poj1050:给一个n*n(1<=n<=100)的矩阵,求最大子矩阵和

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int mp[100][100];
int temp[200];
const  int mod = 1e9+7;int solve(int *a,int n)
{int dp = 0,Max = 0;for(int i = 0; i < n; i++){if(dp > 0) dp += a[i];else dp = a[i];Max = max(Max, dp);}return Max;
}int main()
{#ifdef xxzfreopen("in.txt","r",stdin);#endif // xxzint n;while(~scanf("%d",&n)){for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)cin>>mp[i][j];int max_ans = 0;for(int i = 0; i < n; i++){memset(temp,0,sizeof(temp));for(int j = i;j < n; j++){for(int k = 0; k < n; k++)temp[k] += mp[j][k];int ans = solve(temp,n);max_ans = max(max_ans,ans);}}cout<<max_ans<<endl;}return 0;
}

HDU1559:给出n*m（0< n,m<=1000）的矩阵，求规格为x*y的小矩阵最大和为多少。
这题相比上题增加了限制条件，也就是上面那种的特殊情况，如用上面算法时间复杂度是O(n*n*m)则会超时，由于题目对小矩阵有了限制，我们可以用DP做，令a[i][j]为1<=s<=i，1<=t<=j所有元素的和，可以在线处理，那么就可以通过加减来求出当前子矩阵和，就好像计算几个矩阵面积一样（某部分覆盖在一起，所以相加后减去重复的面积）。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int mp[1000][1000];
int temp[200];
const  int mod = 1e9+7;int solve(int *a,int n)
{int dp = 0,Max = 0;for(int i = 0; i < n; i++){if(dp > 0) dp += a[i];else dp = a[i];Max = max(Max, dp);}return Max;
}int main()
{
#ifdef xxzfreopen("in.txt","r",stdin);
#endif // xxzint T;scanf("%d",&T);while(T--){int n,m,x,y;cin>>n>>m>>x>>y;int Max = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin>>mp[i][j];mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1];if(i >= x && j >= y){int ans = mp[i][j] - mp[i-x][j] - mp[i][j-y] + mp[i-x][j-y];Max = max(Max,ans);}}}cout<<Max<<endl;}return 0;
}

其实这题还可以用数状数组做，二维的裸题

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int S;int mp[1200][1200];
int lowbit(int x)
{return x & -x;
}int  getsum(int x,int y)
{int  sum  = 0;for(int i  = x; i > 0; i -= lowbit(i))for(int j = y; j > 0; j -= lowbit(j)){sum += mp[i][j];}return sum;
}void update(int x,int y,int value)
{for(int i = x; i <= 1200; i += lowbit(i))for(int j = y; j <=1200 ; j += lowbit(j)){mp[i][j] += value;}
}int main()
{#ifdef xxzfreopen("in","r",stdin);#endif // xxzint T;scanf("%d",&T);while(T--){int m,n,x,y;scanf("%d%d%d%d",&m,&n,&x,&y);memset(mp,0,sizeof(mp));for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){int temp;scanf("%d",&temp);update(i,j,temp);}}int ans = -1;for(int i = x; i <= m; i++){for(int j = y; j <= n; j++){ans = max(ans,getsum(i,j) - getsum(i-x,j)-getsum(i,j-y) + getsum(i-x,j-y));}}printf("%d\n",ans);}return 0;
}