#面试题 17.24. 最大子矩阵

• LeetCode：面试题 17.24. 最大子矩阵
• 难度：困难
• 归类：数组、动态规划、矩阵、前缀和
• 主解法：枚举上下边界 + 列和压缩 + Kadane

#先给结论

固定子矩阵的上边界 top 和下边界 bottom 后，把这几行按列求和：

columnSums[column] = matrix[top][column] + ... + matrix[bottom][column]

此时选择连续列 [left, right] 的总和，恰好等于二维子矩阵：

[top, left, bottom, right]

的元素和。二维问题因此转化为一维最大子数组问题，可以用 Kadane 算法在线性时间求解，并同时记录左右端点。

枚举 O(rows²) 组上下边界，每组执行 O(columns) 的列和更新和 Kadane，总时间复杂度为：

O(rows² × columns)

#题目描述

给定一个由正整数、负整数和 0 组成的矩阵，找出元素和最大的非空子矩阵。

返回：

[r1, c1, r2, c2]

其中：

• (r1, c1) 是左上角坐标。
• (r2, c2) 是右下角坐标。
• 四个坐标都是从 0 开始的闭区间端点。
• 如果有多个最大和子矩阵，返回任意一个即可。

示例：

输入：
[
  [-1,  0],
  [ 0, -1]
]

输出：[0, 1, 0, 1]

坐标 [0, 1, 0, 1] 表示只选择右上角的 0。返回 [1, 0, 1, 0] 也同样正确。

题目约束：

1 <= matrix.length, matrix[0].length <= 200

所以矩阵一定非空。

#从二维降成一维

假设固定：

top = 1
bottom = 3

将第 1～3 行按列相加后得到：

columnSums = [a, b, c, d, ...]

那么：

• columnSums[0] 是原矩阵第 1～3 行、第 0 列的和。
• columnSums[left] + ... + columnSums[right] 是原矩阵第 1～3 行、第 left～right 列的矩形和。

因此，固定上下边界后，只需在 columnSums 中寻找最大连续子数组。

为了避免每换一个 bottom 都重新求和，固定 top 后令 columnSums 初始全为 0，再逐行累加：

bottom = top      加入 matrix[top]
bottom = top + 1  再加入 matrix[top + 1]
bottom = top + 2  再加入 matrix[top + 2]
...

每扩展一次下边界只需 O(columns)。

#1. dp 数组含义

对固定的 [top, bottom]，定义一维 DP：

dp[right] = 在 columnSums 中，以 right 位置结尾的最大连续子数组和

为了恢复坐标，还需要知道这个连续子数组从哪一列开始。

代码不保存完整 dp 数组，而是使用：

• currentSum：扫描到当前 right 时，以 right 结尾的最大连续子数组和，即压缩后的 dp[right]。
• currentLeft：currentSum 对应连续子数组的左端点。
• bestSum：到目前为止所有上下边界和左右区间中的最大和。
• answer：bestSum 对应的 [top, left, bottom, right]。

columnSums 是二维到一维的压缩状态，currentSum 则是 Kadane DP 的空间压缩。

#2. 确定状态转移方程

以 right 结尾的最大连续子数组只有两种选择：

1. 只选择当前元素 columnSums[right]。
2. 把当前元素接在 dp[right - 1] 后面。

因此：

dp[right] = max(
    columnSums[right],
    dp[right - 1] + columnSums[right]
)

如果此前的 currentSum <= 0，把它接到当前元素前面不会让结果更大，可以从当前列重新开始：

currentSum = columnSums[right]
currentLeft = right

否则继续扩展：

currentSum += columnSums[right]

这里使用 <= 0 而不是 < 0 只会在前缀和恰好为 0 时选择更靠后的等价起点，不影响最大和；题目允许多个答案时返回任意一个。

每次得到新的 currentSum 后，如果它严格大于 bestSum，就记录：

[top, currentLeft, bottom, right]

#3. dp 数组如何初始化

#列压缩数组

每次更换上边界 top 时：

columnSums = new Array(columns).fill(0)

因为还没有加入任何行。

#Kadane 状态

每组 [top, bottom] 开始时：

currentSum = 0
currentLeft = 0

扫描第一列时 currentSum <= 0，所以会正确地从第一列初始化实际状态。

#全局答案

必须使用：

bestSum = -Infinity

不能初始化为 0。题目要求选择非空子矩阵，如果矩阵全为负数，答案应该是数值最大的那个负数，而不是不存在的空矩阵和 0。

例如：

matrix = [
  [-5, -2],
  [-3, -4]
]

正确答案对应单个元素 -2，坐标为 [0, 1, 0, 1]。

#4. 确定遍历顺序

循环顺序为：

枚举 top
    清空 columnSums
    枚举 bottom = top ... rows - 1
        把 matrix[bottom] 累加到 columnSums
        从左到右执行 Kadane

这样有两层复用：

• 固定 top 后，新的 bottom 复用此前的列和。
• Kadane 从左到右时，dp[right] 只复用 dp[right - 1]。

不能在更换 top 后继续使用旧的 columnSums，否则会混入不属于当前上下边界的行。

#5. 举例打印 dp 数组

使用更完整的矩阵：

[
  [ 9, -8,  1,  3, -2],
  [-3,  7,  6, -2,  4],
  [ 6, -4, -4,  8, -7]
]

固定 top = 0，逐步扩展 bottom：

当 top = 0、bottom = 2 时，Kadane 的压缩 DP：

最大和为 19，对应坐标：

[0, 0, 2, 3]

#代码实现

本实现根据题目约束独立整理，使用行区间压缩与 Kadane 算法恢复完整坐标。

#JavaScript 实现

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var getMaxMatrix = function (matrix) {
    const rows = matrix.length;
    const columns = matrix[0].length;

    // 记录目前找到的最大子矩阵和及其坐标
    let bestSum = -Infinity;
    let answer = [0, 0, 0, 0];

    // 枚举子矩阵的上边界
    for (let top = 0; top < rows; top++) {
        // columnSums[column] 表示 top 到 bottom 之间第 column 列的总和
        // 更换上边界后，需要重新从 0 开始累加
        const columnSums = new Array(columns).fill(0);

        // 枚举子矩阵的下边界
        for (let bottom = top; bottom < rows; bottom++) {
            // 将当前 bottom 行加入列和，把二维行区间压缩成一维数组
            for (let column = 0; column < columns; column++) {
                columnSums[column] += matrix[bottom][column];
            }

            // currentSum：当前连续列区间的和
            // currentLeft：当前连续列区间的左边界
            let currentSum = 0;
            let currentLeft = 0;

            // 在 columnSums 中寻找最大连续子数组
            for (let right = 0; right < columns; right++) {
                if (currentSum <= 0) {
                    // 前面的和不大于 0，对后续没有帮助，从当前列重新开始
                    currentSum = columnSums[right];
                    currentLeft = right;
                } else {
                    // 前面的和为正，保留它并继续向右扩展
                    currentSum += columnSums[right];
                }

                // 找到更大的矩形和时，保存完整的上下左右边界
                if (currentSum > bestSum) {
                    bestSum = currentSum;
                    answer = [top, currentLeft, bottom, right];
                }
            }
        }
    }

    // 坐标顺序：[上边界, 左边界, 下边界, 右边界]
    return answer;
};

#边界与陷阱

• 全负矩阵： bestSum 必须初始化为 -Infinity，保证选择一个真实元素。
• 单行矩阵： 问题退化为普通最大子数组。
• 单列矩阵： 枚举上下边界即可覆盖所有连续行区间。
• 全零矩阵： 任意单个 0 都是合法答案，严格 > 会保留最先遇到的答案。
• 坐标顺序： 返回 [上, 左, 下, 右]，不是 [左, 上, 右, 下]。
• 坐标是闭区间： bottom 和 right 都属于子矩阵。
• 更换 top 要清零： columnSums 不能跨上边界复用。
• 扩展 bottom 要累加： 不能直接覆盖上一轮列和。
• Kadane 重启要同步左端点： 只重置和、不重置 currentLeft 会返回错误坐标。
• 多个最优答案： 题目允许任意一个，不需要额外实现字典序或面积规则。

#复杂度分析

设矩阵有 rows 行、columns 列：

• 上、下边界共有 O(rows²) 组。
• 每组边界更新列和并执行 Kadane，各需要 O(columns)。
• 时间复杂度：O(rows² × columns)。
• 空间复杂度：O(columns)，用于 columnSums；Kadane 状态本身为 O(1)。

当行数远大于列数时，可以交换压缩方向：枚举左右边界，把每一行压成一维数组，使复杂度变为 O(columns² × rows)。根据较小维度选择平方项，可得到：

O(min(rows, columns)² × max(rows, columns))

但实现时必须同步转换返回坐标。题目两个维度都不超过 200，当前按行压缩的版本已经足够。