LeetCode.面试题17.24.最大子矩阵详解

问题描述

给定一个正整数、负整数和 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:vector<int> getMaxMatrix(vector<vector<int>>& matrix) {int maxSum = INT_MIN;vector<int> result(4); // 存放最终结果，[r1, c1, r2, c2]int rows = matrix.size(), cols = matrix[0].size();// 遍历所有列的组合for (int left = 0; left < cols; ++left) {vector<int> 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;}
};