本文主要是介绍动态规划3：最大子段和问题到最大子矩阵问题（三）：初探最大子矩阵之和问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。
例子：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其最大子矩阵为：
9 2
-4 1
-1 8
其元素总和为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)
由此我们可以看出最后所求的就是此一维数组的最大子断和问题，到此我们已经将问题转化为上面的已经解决了的问题了。
2、基于最大子段和问题，算出任意n行的和数组，转变成最大字段和进行处理，对于任意n行，如果采用各个处理的话，其时间复杂度相对较高，所以对和数组的处理是本题的又一关键；
3、压缩矩阵
下面举一个简单的例子。在一个一维的数列中，要想求从第i个元素到第j个元素的和，我们可以用这样的方法：设数组sum[i]表示从第1个到第i个元素的和，则：求从第i个元素到第j个元素的和，只需用sum[j]-sum[i]就足够了。由此推广到二维矩阵，设sum[i,j]表示矩阵第j列前i个元素的和，cost[i,j]表示原始数据，则：
压缩数据程序代码为：
for i:=1 to n do
for j:=1 to m do
sum[i,j]:=sum[i-1,j]+cost[i,j];
下一个问题是，如何将数据从压缩的数组中读出。
读取数据代码为：
for i:=0 to n-1 do
for j:=i+1 to n do
for k:=1 to n do temp[k]:=sum[j,k]-sum[i,k];
到此，最大子矩阵问题就完全转换为连续最大和问题。
#include<stdio.h>
#include<string.h>
#define MAXN 105
int main()
{ freopen("C:\\in.txt","r",stdin); int dp[MAXN][MAXN]; int n,t;while (~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); for (int i=1;i<=n;++i) { for (int j=1;j<=n;++j) { scanf("%d",&t); dp[i][j]=dp[i-1][j]+t; } } int max=0; for (int i=1;i<=n;++i) { for (int j=i;j<=n;++j) { int sum=0; for (int k=1;k<=n;++k) { sum+=dp[j][k]-dp[i-1][k]; if (sum<0) sum=0; if (sum>max) max=sum; } } } printf("%d\n",max); } return 0;
} 这篇关于动态规划3：最大子段和问题到最大子矩阵问题（三）：初探最大子矩阵之和问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
