题目描述 ：给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
示例1：
输入：
[
[-1,0],
[0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵
思考 ： 动态规划问题
1、最最最暴力的解法
- 遍历二维数组的每一个点，(r1, c1)，尝试构建一个子矩阵[r1,c1] ~ [r2,c2]（子矩阵左上角到右下角坐标），然后计算这个子矩阵。
- 这一过程的时间复杂度为：O(N6)。遍历二维矩阵需要O(N2)的时间复杂度，构造子矩阵需要O(N2)的时间复杂度，计算子矩阵需要O(N2)的时间复杂度。
- 空间复杂度：O(N2)，可以创建一个二维数组，重复使用。
- 这个解法没有任何可行性，我们考虑进行一定的优化。
2、暴力解法优化一（不单单是这道题，针对二维子矩阵和的问题均可用这样暴力解法，然后再根据题目进一步考虑优化问题）
- 遍历二维数组的每一个点，(r1, c1)，尝试构建一个子矩阵[r1,c1] ~ [r2,c2]（子矩阵左上角到右下角坐标），然后计算这个子矩阵。
- 针对第1点的解法，我们尝试优化计算子矩阵的时间复杂度，将其降为O(1)。
- 我们尝试构建一个四维的dp数组来完成上述的想法，dp[i1][j1][i2][j2]代表子矩阵左上角坐标为(i1, j1)，右下角坐标为(i2, j2)的最大和。
- 状态转移方程（此处利用了容斥原理）:
- dp[i1][j1][i2][j2] = dp[i1][j1][i2-1][j1] + dp[i1][j1][i2][j2-1] - dp[i1][j1][i2-1][j2-1] + matrix[i2][j2]。
- 这一过程的时间复杂度为：O(N4)。遍历二维矩阵需要O(N2)的时间复杂度，构造子矩阵需要O(N2)的时间复杂度，计算子矩阵需要O(1)的时间复杂度。
- 空间复杂度为：O(N4)，空间复杂度太高了，很容易就爆内存了。空间换时间
代码如下（不能AC，14/45）:
class Solution {public int[] getMaxMatrix(int[][] matrix) {int R = matrix.length;int C = matrix[0].length;int[][][][] dp = new int[R+1][C+1][R+1][C+1];int maxSum = Integer.MIN_VALUE;int[] ans = new int[4];int r1 = 0, c1 = 0;for(int i1 = 1; i1 <= R; i1++){for(int j1 = 1; j1<= C; j1++){r1 = i1;c1 = j1;dp[i1][j1][i1][j1] = matrix[i1-1][j1-1];for(int i2 = i1; i2 <= R; i2++){for(int j2 = j1; j2<= C; j2++){dp[i1][j1][i2][j2] = dp[i1][j1][i2][j2-1] + dp[i1][j1][i2-1][j2] -dp[i1][j1][i2-1][j2-1] + matrix[i2-1][j2-1];if(dp[i1][j1][i2][j2] > maxSum){maxSum = dp[i1][j1][i2][j2];ans[0] = r1-1;ans[1] = c1-1;ans[2] = i2-1;ans[3] = j2-1;}}}}}return ans;}}
3、暴力解法优化二
- 由于第 2 点的解法空间复杂度太高，在此尝试进一步优化。
- 我们构造子矩阵都为由 (i1, j1) 开始的，由此设计的状态方程 dp[i1][j1][i2][j2]，但是，每当(i1, j1)发生变化时，dp[i1][j1][][] 与 dp[new_i1][new_j1][][] 之间并无状态转移的联系，所以，我们把状态方程删去前两维，(i1, j1)状态变成隐式了（在前两层 for 循环体现，而不再状态方程中体现），新的状态方程为dp[i2][j2]，在外面两层循环的遍历中，对每一个 (i1, j1) 而言，dp[i2][j2] 仍然可以表示 子矩阵
（左上角为(i1, j1)，右下角为(i2, j2)）的最大和，只是空间层面优化了两维。
- 与第 2 点的时间复杂度一样，空间复杂度优化为O(N2)。
代码如下（不能AC，42/45） ：
class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
int[][] dp = new int[R+1][C+1];
int maxSum = Integer.MIN_VALUE;
int[] ans = new int[4];
int r1 = 0, c1 = 0;
for(int i1 = 1; i1 <= R; i1++){
for(int j1 = 1; j1<= C; j1++){
for(int[] OneDimension : dp){//将二维dp置0
Arrays.fill(OneDimension, 0);
}
r1 = i1;
c1 = j1;
dp[i1][j1] = matrix[i1-1][j1-1];
for(int i2 = i1; i2 <= R; i2++){
for(int j2 = j1; j2<= C; j2++){
dp[i2][j2] = dp[i2][j2-1] + dp[i2-1][j2] -
dp[i2-1][j2-1] + matrix[i2-1][j2-1];
if(dp[i2][j2] > maxSum){
maxSum = dp[i2][j2];
ans[0] = r1-1;
ans[1] = c1-1;
ans[2] = i2-1;
ans[3] = j2-1;
}
}
}
}
}
return ans;
}
}
4、状态压缩（二维DP压缩成一维DP）
- 由上述暴力解法可以得知，时间复杂度为O(N4)，不能 AC 这道题。接下来，我们尝试对时间复杂度进行优化。
- 总结上述暴力解法，可以得出，我们求解子矩阵最大和需要遍历 [i1, j1, i2, j2] 这四个变量，i 和 j 对应两个维度，有这么一种思想，固定住一维，然后关注另一维的变化情况。比如我们可以固定 i1 和 i2，在 i1 和 i2 固定的前提下，我们从 j1 遍历到 j2，这样就可以计算出 在 第 i1 行 到 第 i2 行范围内的最大子矩阵之和（还需要利用一维前缀和算法），然后我们再对 i1 和 i2 做遍历，就能以 O(NNM) 的时间复杂度解决该问题。
- 对于这个解法，还有很多不理解的小细节，比如为什么可以将二维上的前缀和压缩成一维处理，目前没有一个直观的认识，等待继续学习。
- 时间复杂度：O(NNM)，其中 N 为矩阵行数，M 为矩阵列数。
- 空间复杂度：O(M)。
代码如下（AC）:
class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
int[] ans = new int[4];
int row = 0, col = 0; //最大子矩阵左上角坐标
int[] dp = new int[C];
int maxSubMatrixSum = Integer.MIN_VALUE;
for(int r1 = 0; r1 < R; r1++){//枚举行维度的上边界
Arrays.fill(dp, 0);//每更新上边界，dp也需要更新
for(int r2 = r1; r2 < R; r2++){//枚举行维度的下边界
int sum = 0;
for(int c = 0; c < C; c++){//遍历左右边界(列维度)
//进行一维的前缀和问题求解
dp[c] += matrix[r2][c];
if(sum > 0){
//一维dp中有 dp[i] = max{dp[i-1]+nums[i], nums[i]}
//因此，上式中的赋值取决于dp[i-1] > 0
//在此处，Sum就等于 dp[i-1]
sum += dp[c];
}else{
//放弃之前的前缀和，从新计算
//顺带维护最大子矩阵左上角坐标
sum = dp[c];
row = r1;
col = c;
}
if(sum > maxSubMatrixSum){
maxSubMatrixSum = sum;
ans[0] = row;
ans[1] = col;
//ans[2]~ans[3]为最大子矩阵右下角坐标
ans[2] = r2;
ans[3] = c;
}
}
}
}
return ans;
}
}
若有收获，就点个赞吧
0 人点赞
