seo2短视频发布,wordpress商品分类标题seo,低代码快速开发平台,郑州中心城区文章目录1. 题目2. 解题2.1 前缀和#xff08;超时#xff09;2.2 动态规划1. 题目
给定一个正整数和负整数组成的 N M 矩阵#xff0c;编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]#xff0c;其中 r1, c1 分别代表子矩阵左上角的行号和列号超时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. 解题
类似题目 LeetCode 363. 矩形区域不超过 K 的最大数值和DPset二分
2.1 前缀和超时
求出每个位置与(0,0)构成的子矩阵的和4层 for 循环遍历左上角为x,y右下角为ij的子矩阵其和为 sumprefixsum[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]sumprefixsum[i][j]−prefixsum[x−1][j]−prefixsum[i][y−1]prefixsum[x−1][y−1]复杂度 O(m2n2)O(m^2n^2)O(m2n2)通过14/25个测试
class Solution {
public:vectorint getMaxMatrix(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size(), i, j, x, y;int sum, maxSum INT_MIN;vectorvectorint 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(i0 j0)prefixsum[i][j] - prefixsum[i-1][j-1];// cout prefixsum[i][j] ;}// cout endl;}vectorint 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(m2n)O(m^2n)O(m2n)
class Solution {
public:vectorint getMaxMatrix(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size(), i, j, k, l, r;int sum, maxSum INT_MIN;vectorint sumRi_Rj(n);//【ij】行的列向和vectorint 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
