#|leetcode面试题 17.24. 最大子矩阵/动态规划 #|算法

文章目录

题目：面试题 17.24. 最大子矩阵
基本思想：动态规划

题目：面试题 17.24. 最大子矩阵给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动
示例:

输入: [ [-1,0], [0,-1] ] 输出: [0,1,0,1] 解释: 输入中标粗的元素即为输出所表示的矩阵

说明：

1 <= matrix.length, matrix[0].length <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-submatrix-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
基本思想：动态规划这道题是最大子段和的延伸，将一维变为的二维。
求解思路：将二维降维成一维，利用最大子段和的思想进行求解

将矩阵压缩：也就是求每一列的前缀和（前i个元素的和）
求任意两行之间的最大子矩阵和（最大子段和的思想）
因为这里要确定最大子矩阵的左上角和右下角的位置，所以在第2步求解的过程中记录子矩阵的起始列

【#|leetcode面试题 17.24. 最大子矩阵/动态规划】说明：这道题B站上小旭讲的超级明白，参考链接：视频链接

class Solution { public: vector getMaxMatrix(vector>& matrix) { int row = matrix.size(), col = matrix[0].size(); int part_sum[col][row + 1]; //求每一列的前缀和 for(int i = 0; i < col; ++i){ part_sum[i][0] = 0; for(int j = 0; j < row; ++j){ part_sum[i][j + 1] = part_sum[i][j] + matrix[j][i]; } } int res = INT_MIN; vector result(4); //求任意两行之间的最大子矩阵和 for(int i = 0; i < row; ++i){ for(int j = i; j < row; ++j){ int s_col = 0; //起始列为0 int dp = 0; for(int k = 0; k < col; ++k){//终止列 if(dp > 0){ dp += part_sum[k][j + 1] - part_sum[k][i]; } else{ s_col = k; dp = part_sum[k][j + 1] - part_sum[k][i]; } if(dp > res){ res = dp; result = {i, s_col, j, k}; } } } } return result; } }; /* 这道题是最大子段和的延伸，基本思路：将这道题转化为最大子段和 1.将二维数组压缩成一维数组，就可以用最大子段和的动态规划思路；压缩方法：求每一列的前i个元素的和 2.然后求任意[i,j]行所构成的最大子矩阵*/