问题描述

给定一个正整数、负整数和 0 组成的 N × M 矩阵,编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2],其中 r1c1 分别代表子矩阵左上角的行号和列号,r2c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵,返回任意一个均可。

解题思路

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;
    }
};
07-07 08:52