【题目链接】
ybt 1224：最大子矩阵
ybt 1282：最大子矩阵
OpenJudge 2.6 1768:最大子矩阵
洛谷 P1719 最大加权矩形
【题目考点】
1. 动态规划：线性动规
2. 前缀和
【解题思路】
求二维最大子矩阵和，与其相对的一维问题为求最大子段和。
我们可以思考将该二维问题降维为一维问题，而后就是一个求最大子段和的问题了。
记第
(
i
,
j
)
(i,j)
(i,j)位置元素的值为
a
i
,
j
a_{i,j}
ai,j
遍历每一种可能的
i
1
i_1
i1与
i
2
i_2
i2的组合，共有
n
(
n
+
1
)
/
2
n(n+1)/2
n(n+1)/2种情况
i
1
=
1
i_1=1
i1=1时
i
2
i_2
i2可以取
1
∼
n
1\sim n
1∼n，共
n
n
n种情况
i
1
=
2
i_1=2
i1=2时
i
2
i_2
i2可以取
2
∼
n
2\sim n
2∼n，共
n
−
1
n-1
n−1种情况
…
i
1
=
n
i_1=n
i1=n时
i
2
i_2
i2可以取
1
n
1n
1n，共
1
1
1种情况
一共有
1
+
2
+
.
.
.
+
n
=
n
(
n
+
1
)
/
2
1+2+...+n = n(n+1)/2
1+2+...+n=n(n+1)/2种情况
假设考察的子矩阵左上角位置为
(
i
1
,
j
1
)
(i_1,j_1)
(i1,j1)，右下角位置为
(
i
2
,
j
2
)
(i_2,j_2)
(i2,j2)
在
i
1
i_1
i1与
i
2
i_2
i2确定后，只能改变
j
1
j_1
j1或
j
2
j_2
j2，求最大子矩阵和。
如果将每列加和后，作为一个一维数组
b
b
b的元素，那么该问题就变成了求一维数组
b
b
b的最大子段和。
将子矩阵压缩成一维数组
b
b
b，
b
j
b_j
bj为该子矩阵第
j
j
j列元素的加和，即：
b
j
=
∑
i
=
i
1
i
2
a
i
,
j
b_j=\sum_{i=i_1}^{i_2}a_{i,j}
bj=∑i=i1i2ai,j
纵向看，
b
j
b_j
bj也是一个一维子段和，可以用前缀和方便求出。
记
s
i
,
j
s_{i,j}
si,j为第j列第
1
∼
i
1\sim i
1∼i行元素的加和，那么
b
j
=
s
i
2
,
j
−
s
i
1
−
1
,
j
b_j=s_{i_2,j}-s_{i_1-1,j}
bj=si2,j−si1−1,j
接下来求一维数组
b
b
b的最大子段和。
求最大子段和的方法可以参考：洛谷 P1115 最大子段和
有使用双指针、线性动规、前缀和的方法。
复杂度分析：
求前缀和不需要额外复杂度，可以一边输入一边求。
选择
i
1
i_1
i1与
i
2
i_2
i2一共有
n
(
n
+
1
)
/
2
n(n+1)/2
n(n+1)/2种情况，复杂度
O
(
n
2
)
O(n^2)
O(n2)，每种情况下求数组b复杂度为
O
(
n
)
O(n)
O(n)，求最大子段和复杂度为
O
(
n
)
O(n)
O(n)，总体复杂度为
O
(
n
3
)
O(n^3)
O(n3)
本题n为100，
O
(
n
3
)
O(n^3)
O(n3)是可以接受的。
【题解代码】
解法1：二维变一维，双指针求最大子段和
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
int n, a[N][N], b[N], s[N][N];//b[j]:子矩阵第j列的加和 s[i][j]:第j列的第1行到第i行的元素加和
int mx = -INF;
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
cin >> a[i][j];
s[i][j] = s[i-1][j] + a[i][j];
}
for(int i1 = 1; i1 <= n; ++i1)//子矩阵第一行为原矩阵的第i1行，最后一行为原矩阵的第i2行
for(int i2 = i1; i2 <= n; ++i2)
{
for(int j = 1; j <= n; ++j)
b[j] = s[i2][j] - s[i1-1][j];
int sum = 0;
for(int j = 1; j <= n; ++j)//双指针法求最大子段和
{
if(sum < 0)
sum = b[j];
else
sum += b[j];
mx = max(mx, sum);
}
}
cout << mx;
return 0;
}
解法2：二维变一维，线性动规求最大子段和
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
int n, a[N][N], b[N], s[N][N];//b[j]:子矩阵第j列的加和 s[i][j]:第j列的第1行到第i行的元素加和
int mx = -INF;
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
cin >> a[i][j];
s[i][j] = s[i-1][j] + a[i][j];
}
for(int i1 = 1; i1 <= n; ++i1)//子矩阵第一行为原矩阵的第i1行，最后一行为原矩阵的第i2行
for(int i2 = i1; i2 <= n; ++i2)
{
for(int j = 1; j <= n; ++j)
b[j] = s[i2][j] - s[i1-1][j];
int dp[N] = {};//线性动规求最大子段和
for(int j = 1; j <= n; ++j)
{
dp[j] = max(b[j], dp[j-1]+b[j]);
mx = max(mx, dp[j]);
}
}
cout << mx;
return 0;
}
