A1282 最大子矩阵

和A1224一模一样

题意

给你一个矩阵，求里面元素和最大的子矩阵，输出这个和。

题解

引理

先求最大连续子序列~ 对于一个数组b，求最大连续子序列和。 状态转移方程为dp[i]=max(b[i],b[i]+dp[i-1])。 dp[i]表示对于位置i，包含它的子序列最大值。 实际上，对于位置i，最大连续子序列和是b[i]（不包含前面最大子序列）和b[i]+dp[i-1]（包含前面最大）的最大值。最后求dp数组里最大的数，即为答案。

样例分析

用a数组存矩阵

输入：

4
0 -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

输出：15

首先，分别求每行的最大连续子序列：

4
0 -2 -7  0//最大为0
9  2 -6  2//最大为11
-4  1 -4  1//最大为1
-1  8  0 -2//最大为8
最大为11

然后，求两行在一起的最大子序列，将上下两行加起来，用b数组来存：

4
0 -2 -7  0
9  2 -6  2//9 0 -13 2，最大为9
-4  1 -4  1//5 3 -10 3，最大为8
-1  8  0 -2//-5 9 -4 -1，最大为9
最大为9

继续求三行，四行在一起的最大子序列。 用ans求出最大的值，就是答案了。

呆马

#include<bits/stdc++.h>
using namespace std;
int a[105][105],b[105][105],dp[105],ans,n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		cin>>a[i][j];//a数组存储矩阵
	}
	for(int i=1;i<=n;i++){
		memset(b,0,sizeof(b));//初始化b数组
		for(int j=i;j<=n;j++){
			for(int k=1;k<=n;k++)
			b[j][k]=a[j][k]+b[j-1][k];//求出从1到n行加在一起的数组
			memset(dp,0,sizeof(dp));//初始化dp数组
			for(int k=1;k<=n;k++){
				dp[k]=max(b[j][k],b[j][k]+dp[k-1]);//由引理得(没看懂再回去看一遍）
				ans=max(ans,dp[k]);//求最大值
			}
		}
	}
	cout<<ans<<endl;//输出答案
	return 0;
}

点赞！！！！！！！

关于“如何做”，C23liupeilin 的题解已经说得很详细了，我就不画蛇添足了。我在这里主要是想说说“为什么”这样做。

首先，如果最终求出的最大子矩阵 $C$ 只有一行，显然问题可以归化到最大子段和，因为它可能会出现在原矩阵 $A$ 的任何一行，那么要求它的所有元素之和（即 $A$ 的最大子矩阵和），只需要把 $A$ 看作 $n$ 行长度为 $n$ 的向量（一维数组），对每一行求其最大子段和，然后 max 这 $n$ 个最大子段和，就是答案。

那么，如果 $C$ 有两行呢？它的元素之和怎么求？注意到：

• $C$ 占据 $A$ 中的连续两行，要遍历检查 $n-1$ 种情况（$A$ 中连续两行，有 $n-1$ 种情况）；
• $C$ 的所有元素之和，等于 $C$ 的第一行元素之和再加上第二行元素之和。

在求 $C$ 的时候，要把 $C$ 的两行合并，“降维”到一维，综合考虑，才能求得最大和（单独只考虑 $C$ 的某一行肯定是不行的）。在降维的时候，$A$ 中相应的两行也要一起降维考虑：也就是说，必须依次把 $A$ 的相邻两行相加，“合并”成一行，求出合并行的最大子段和，这样就能遍历 $C$ 可能的所有情况。最后对所有合并行的最大子段和取 max，就能得到答案。

依此类推，若 $C$ 有三行，要依次合并考虑 $A$ 中的相邻三行。

说明完毕。你可以自己举一个最大子矩阵是两行的样例，手推一遍，然后再扩展到三行的情况，应该就能明白了。

不明白我好像也没辙，再修炼一下吧

有不懂的欢迎评论区讨论。

我会去后台看到底是谁给我点差评