最大子矩阵和问题

题目描述

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为 $1 \times 1$ 或更大的连续子阵列。

矩形的总和是该矩形中所有元素的总和。

在这个问题中，具有最大和的子矩形被称为最大子矩形。

输入格式

输入中将包含一个 $N \times N$ 的整数数组。

第一行只输入一个整数 $N$，表示方形二维数组的大小。

从第二行开始，输入由空格和换行符隔开的 $N^2$ 个整数，它们即为二维数组中的 $N^2$ 个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。

数组中的数字会保持在 $[-127,127]$ 的范围内。

输出格式

输出一个整数，代表最大子矩形的总和。

输入输出样例 #1

输入样例

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

输出样例

15

输入输出样例 #2

输入样例

3
1 2 3
4 5 6
7 8 9

输出样例

45

限制条件

• $1 \le N \le 100$
• 数组元素范围：$[-127, 127]$

样例解释 #1

矩阵为：

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

最大子矩阵为：

9 2
-4 1
-1 8

和为：$9 + 2 + (-4) + 1 + (-1) + 8 = 15$

解题思路

这是一个二维的最大子段和问题（最大子矩阵和）。对于 $N \le 100$，有多种解法：

方法一：暴力枚举（$O(N^4)$）

枚举所有可能的子矩阵：左上角 $(x1, y1)$ 和右下角 $(x2, y2)$，计算子矩阵和，取最大值。

• 时间复杂度：$O(N^4)$，对于 $N=100$，$100^4 = 10^8$，可能会超时

方法二：优化枚举（$O(N^3)$）

使用前缀和优化：

1. 计算二维前缀和 $prefix[i][j]$，表示从 $(1,1)$ 到 $(i,j)$ 的子矩阵和
2. 枚举子矩阵的上边界 $i$ 和下边界 $j$（$O(N^2)$）
3. 对于固定的上下边界，将这一列区间的和压缩成一个一维数组（$O(N)$）
4. 在一维数组上求最大子段和（$O(N)$）
5. 总时间复杂度：$O(N^3)$，对于 $N=100$，$100^3 = 10^6$，可以接受

方法三：动态规划（$O(N^3)$）

类似方法二，但使用不同的压缩方式。

算法步骤（$O(N^3)$ 方法）

1. 输入 $N$ 和矩阵
2. 计算二维前缀和
3. 初始化最大和为矩阵中的最小值
4. 枚举上边界 $i$（$1$ 到 $N$）
5. 枚举下边界 $j$（$i$ 到 $N$）
6. 对于每一列 $k$，计算第 $k$ 列从第 $i$ 行到第 $j$ 行的和： $colSum[k] = prefix[j][k] - prefix[i-1][k]$
7. 在 $colSum$ 数组上求最大子段和
8. 更新全局最大和
9. 输出最大和

注意：由于元素可能为负数，最大子矩阵和至少包含一个元素。