程序员面试金典 - 面试题 17.24. 最大子矩阵（转成一维最大子序和 DP）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 17.24. 最大子矩阵（转成一维最大子序和 DP），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2700字，纯文字阅读大概需要4分钟。

内容图文

文章目录

• 1. 题目
• 2. 解题
• 2.1 前缀和（超时）
• 2.2 动态规划

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. 解题

2.1 前缀和（超时）

• 求出每个位置与(0,0)构成的子矩阵的和
• 4层 for 循环遍历左上角为（x,y），右下角为（i，j）的子矩阵
• 其和为 $sum = prefixsum[i][j]-prefixsum[x-1][j]-prefixsum[i][y-1]+prefixsum[x-1][y-1]$sum=prefixsum[i][j]?prefixsum[x?1][j]?prefixsum[i][y?1]+prefixsum[x?1][y?1]
• 复杂度 $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 152. 乘积最大子序列（DP）
本题参考：LeetCode 53. 最大子序和（动态规划），本质一样。

• 2层for循环先把所有可能的行组合找出来
• 然后列向求和，压扁它
• 对这个压扁的一维数组求最大子序和即可
• 时间复杂度 $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

内容总结

以上是互联网集市为您收集整理的程序员面试金典 - 面试题 17.24. 最大子矩阵（转成一维最大子序和 DP）全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 17.24. 最大子矩阵（转成一维最大子序和 DP）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---