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;
    }
};

LeoLei8060