程序员面试金典 - 面试题 17.24. 最大子矩阵（转成一维最大子序和 DP）
程序员面试金典 - 面试题 17.24. 最大子矩阵（转成一维最大子序和 DP）
Michael阿明
发布于 2020-07-13 15:35:50
发布于 2020-07-13 15:35:50
1. 题目
给定一个正整数和负整数组成的 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
类似题目： LeetCode 363. 矩形区域不超过 K 的最大数值和（DP+set二分）
2.1 前缀和（超时）
- 求出每个位置与(0,0)构成的子矩阵的和
- 4层 for 循环遍历左上角为（x,y），右下角为（i，j）的子矩阵
- 其和为 sum=prefixsumi−prefixsumx−1−prefixsumi+prefixsumx−1sum = prefixsumi-prefixsumx-1-prefixsumi+prefixsumx-1sum=prefixsumi−prefixsumx−1−prefixsumi+prefixsumx−1
- 复杂度 O(m2n2)O(m^2n^2)O(m2n2)，通过14/25个测试
class Solution {
public:
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size(), i, j, x, y;
int sum, maxSum = INT_MIN;
vector<vector<int>> prefixsum(matrix);
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if(i > 0)
prefixsum[i][j] += prefixsum[i-1][j];
if(j > 0)
prefixsum[i][j] += prefixsum[i][j-1];
if(i>0 && j>0)
prefixsum[i][j] -= prefixsum[i-1][j-1];
// cout << prefixsum[i][j] << " ";
}
// cout << endl;
}
vector<int> ans(4);
for(i = 0; i < m; i++)
{
for(j = 0; j < n; ++j)
{
for(x = 0; x <= i; x++)
{
for(y = 0; y <= j; y++)
{
sum = prefixsum[i][j];
if(x > 0)
sum -= prefixsum[x-1][j];
if(y > 0)
sum -= prefixsum[i][y-1];
if(x > 0 && y > 0)
sum += prefixsum[x-1][y-1];
if(sum > maxSum)
{
maxSum = sum;
ans[0] = x, ans[1] = y;
ans[2] = i, ans[3] = j;
}
}
}
}
}
return ans;
}
};2.2 动态规划
类似题目：
本题参考：LeetCode 53. 最大子序和（动态规划），本质一样。
- 2层for循环先把所有可能的行组合找出来
- 然后列向求和，压扁它
- 对这个压扁的一维数组求最大子序和即可
- 时间复杂度 O(m2n)O(m^2n)O(m2n)
class Solution {
public:
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size(), i, j, k, l, r;
int sum, maxSum = INT_MIN;
vector<int> sumRi_Rj(n);//【i，j】行的列向和
vector<int> ans(4);
for(i = 0; i < m; ++i)
{
sumRi_Rj.clear();
sumRi_Rj.resize(n,0);
for(j = i; j < m; ++j)
{
for(k = 0; k < n; ++k)
{
sumRi_Rj[k] += matrix[j][k];//列向和
}
//一维dp，初始化
sum = sumRi_Rj[0];
l = r = 0;
if(sum > maxSum)
{
maxSum = sum;
ans[0] = i, ans[1] = l;
ans[2] = j, ans[3] = r;
}
for(k = 1; k < n; ++k)
{ //转为一维数组sumRi_Rj最大子数组和
if(sum > 0)
{
sum += sumRi_Rj[k];
r = k;
}
else
{
sum = sumRi_Rj[k];
l = r = k;
}
if(sum > maxSum)
{
maxSum = sum;
ans[0] = i, ans[1] = l;
ans[2] = j, ans[3] = r;
}
}
}
}
return ans;
}
};384 ms 12.7 MB
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-04-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录