# 最大子矩阵给定一个 $ntimes n$ 的矩阵任意选择其连续的 $a$$0le ale n$行与 $b$$0le ble n$列所确定的一个更小的矩阵就叫作一个子矩阵。一个子矩阵的得分为其每个元素之和请求出原矩阵的最大子矩阵的得分。## 输入格式从标准输入读入数据。第一行一个正整数 $n$$1le nle 200$代表矩阵大小。接下来输入 $n$ 行每行 $n$ 个整数 $a_ij$$a_i

暴力枚举肯定过不了，考虑优化。

对于一个子矩阵，我们可以通过枚举其上下边界，然后再枚举左右边界，来计算其得分。这个过程可以用前缀和优化到 $O(n^3)$。

但是，我们还可以更进一步。考虑到一个子矩阵的得分是其元素之和，我们可以把矩阵的每一列压缩成一个数，然后对压缩后的数列求最大子段和，就可以得到最大子矩阵的得分。这个过程可以用类似于前缀和的思想优化到 $O(n^2)$。

具体来说，我们可以先预处理出矩阵的前缀和 $s_{i,j}$，其中 $s_{i,j}$ 表示矩阵的左上角为 $(1,1)$，右下角为 $(i,j)$ 的子矩阵的元素之和。然后，对于每一列 $j$，我们可以将其压缩成一个数 $a_j$，其中 $a_j=s_{i,j}-s_{i-1,j}$，其中 $i$ 是当前枚举的上边界。然后，我们对 $a_1,a_2,\cdots,a_n$ 求最大子段和，就可以得到当前枚举的子矩阵的得分。最后，我们取所有子矩阵得分的最大值即可。

时间复杂度 $O(n^3)$。

C++ 代码