德阳市建设局网站地址,制作酒店网站,可以做硬件外包项目的网站,域名购买后还要解析吗问题描述
给定一个正整数、负整数和 0 组成的 N M 矩阵#xff0c;编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]#xff0c;其中 r1, c1 分别代表子矩阵左上角的行号和列号#xff0c;r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵…问题描述
给定一个正整数、负整数和 0 组成的 N × M 矩阵编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]其中 r1, c1 分别代表子矩阵左上角的行号和列号r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵返回任意一个均可。
解题思路
1. 基础概念Kadane算法
首先我们需要了解Kadane算法这是一种用于在一维数组中找到最大子数组和的算法。给定一个数组该算法可以找到一个连续子数组其元素之和最大并且能返回这个最大和。
2. 将问题从二维转化为一维
要在二维矩阵中寻找最大子矩阵和我们可以通过固定列的起始和结束点来将问题简化为一维问题
固定列界限选择两个列的索引left和right使得这两个索引之间的所有列都被包含在内。累加行元素对于每个行计算从left列到right列的元素和得到一个新的“行和数组”。例如如果left和right都是1即第二列那么行和数组中的每个元素就是原矩阵该行第二列的元素。
3. 应用Kadane算法到行和数组
对每一个固定的列对left和right我们都得到了一个行和数组。接下来
使用Kadane算法将Kadane算法应用于行和数组找出这个数组中的最大子数组和以及对应的起始行和结束行。记录最大和及其位置如果这次的最大子数组和大于之前记录的最大值更新最大值和相应的行和列索引。这些索引就确定了最大子矩阵的边界。
4. 处理所有可能的列对
从第一列开始逐一将每列作为起始列然后对每个可能的结束列重复上述过程。这意味着我们首先固定起始列然后让结束列从起始列开始向右延伸至矩阵的最后一列对每种情况都计算行和数组然后应用Kadane算法。
5. 输出最终结果
在所有列对组合被考虑之后全局记录的最大值及其对应的子矩阵边界就是我们的答案。这些信息可以用来标识出具有最大和的子矩阵。
代码实现
class Solution {
public:vectorint getMaxMatrix(vectorvectorint matrix) {int maxSum INT_MIN;vectorint result(4); // 存放最终结果[r1, c1, r2, c2]int rows matrix.size(), cols matrix[0].size();// 遍历所有列的组合for (int left 0; left cols; left) {vectorint rowSum(rows, 0); // 初始化行和数组for (int right left; right cols; right) {// 计算从left到right列的行和for (int i 0; i rows; i) {rowSum[i] matrix[i][right];}// 应用Kadane算法找到最大的子数组和及其索引int currentMax INT_MIN, tempSum 0;int rowStart 0, tempRowStart 0, rowEnd 0;for (int i 0; i rows; i) {if (tempSum 0) {tempSum rowSum[i];tempRowStart i;} else {tempSum rowSum[i];}if (tempSum currentMax) {currentMax tempSum;rowStart tempRowStart;rowEnd i;}}// 更新全局最大和及对应的子矩阵坐标if (currentMax maxSum) {maxSum currentMax;result {rowStart, left, rowEnd, right};}}}return result;}
};
