P4204. 最大子矩阵和

解题思路

如何表示一个子矩阵

一个子矩阵可以由四个参数决定，分别为上底、下底、左宽、右宽，分别用变量 a、b、c、d 表示。

如果要枚举所有子矩阵，只需要分别枚举 a、b、c、d，写一个 4 层嵌套的 for 循环即可：

暴力解法

暴力解法很容易想到：枚举所有子矩阵，然后对每个子矩阵内所有元素求和。其核心代码如下：

这里会出现 6 层 for 循环嵌套，时间复杂度较高。由于数据范围为 (1 <= n, m <= 10)，取最大值时复杂度约为 O(n³·m³)。在数据量较大时可能无法通过全部用例，因此需要思考如何优化。

二维前缀和优化

> 注意：该方法与 经典题型「二维区域和检索 - 矩阵不可变」类似。

每个子矩阵的和都可以通过以下方式拆解：

拆解后的四个区域有一个共同特点：它们的上底均为上边界、左宽均为左边界。

因此，可以借鉴一维前缀和的思路，将所有上底为上边界、左宽为左边界（即 a = 0，c = 0）的子矩阵的和提前记录在二维前缀和矩阵 pre_sum_mat 中。

pre_sum_mat 是一个大小为 (n+1) * (m+1) 的矩阵，其中 pre_sum_mat[i][j] 表示以第 0 行、第 0 列为开头（闭区间），第 i 行、第 j 列为结尾（开区间）的子矩阵的和。

上述四个区域的和可以分别用以下方式表示：

• pre_sum_mat[b+1][d+1]
• pre_sum_mat[b+1][c]
• pre_sum_mat[a][d+1]
• pre_sum_mat[a][c]

> 对开/闭区间的理解非常重要，如果理解不清，后续代码很容易出错。

如果把子矩阵用类似切片的方式（不严谨写法）表示为 mat[a:b+1][c:d+1]，那么上述分析过程可以写成：

因此，在原矩阵 mat 中，以 a、b、c、d 分别为上底、下底、左宽、右宽的子矩阵的和可以记为：

上述计算的时间复杂度为 O(1)，因此这种方法规避了暴力解中子矩阵求和时的重复计算，降低了最内层求和的时间复杂度。加上外层循环后，代码如下：

如果不想让最内层的索引出现 +1，可以修改 for 循环的范围：

上述过程的时间复杂度为 O(n²·m²)。当 n、m 取最大值时，复杂度约为 10⁴，可以通过全部用例。

二维前缀和矩阵的构建

二维前缀和矩阵 pre_sum_mat 的构建也要用到类似的拆分过程，其核心代码如下：

要特别注意，二维前缀和 pre_sum_mat 的大小在两个维度上均比原矩阵 mat 大 1。该过程的时间复杂度为 O(n·m)。

代码

解法一：二维前缀和