最大子矩阵和问题（二维矩阵中的最大子矩阵和，可通过压缩为行区间求解）

题目描述
给定一个 m x n 的二维整数矩阵，找到其中元素之和最大的子矩阵，并返回这个最大和。
例如，矩阵如下：

[ 1,  2, -1, -4, -20]
[-8, -3,  4,  2,   1]
[ 3,  8, 10,  1,   3]
[-4, -1,  1,  7,  -6]

最大子矩阵（用粗体标出）为：

[ 1,  2, -1, -4, -20]
[-8, -3,  4,  2,   1]
[ 3,  8, 10,  1,   3]
[-4, -1,  1,  7,  -6]

最大和为 29（子矩阵为从第2行到第4行，第1列到第4列的部分，即包含元素 -3,4,2,1,8,10,1,1,1,7 的矩阵）。

核心思路
这个题目虽然是在二维矩阵中找最大子矩阵，但可以通过“压缩”为多个一维数组的最大子数组和问题来求解。思路是：

1. 枚举子矩阵的上下边界（即起始行和结束行）。
2. 对于每一对上下边界，将这几行的元素按列相加，得到一个一维数组，这个数组的每个元素是原始矩阵中对应列在选定行范围内的和。
3. 在这个一维数组上，用经典的最大子数组和算法（Kadane算法）求出最大和，这个和就对应了以当前上下边界约束下的最大子矩阵和。
4. 所有上下边界组合得到的最大和中的最大值，就是最终答案。

详细步骤

步骤1：理解如何“压缩”行区间
假设我们选择上边界为 rowStart，下边界为 rowEnd（0 ≤ rowStart ≤ rowEnd < m）。
对于每一列 j（0 ≤ j < n），计算从第 rowStart 行到第 rowEnd 行在该列上的元素和，记为 colSum[j]。
即：

\[\text{colSum}[j] = \sum_{i=\text{rowStart}}^{\text{rowEnd}} \text{matrix}[i][j] \]

这样，我们将一个 (rowEnd - rowStart + 1) 行 × n 列 的子矩阵，压缩成了一个长度为 n 的一维数组 colSum。

步骤2：在一维数组上求最大子数组和
对于得到的 colSum 数组，我们要求它的最大子数组和。这可以用 Kadane 算法在 O(n) 时间内完成。
Kadane 算法的基本思想是维护两个变量：

• currentMax：以当前元素结尾的最大子数组和。
• globalMax：全局最大子数组和。
  递推公式：

\[\text{currentMax} = \max(\text{colSum}[j], \ \text{currentMax} + \text{colSum}[j]) \]

\[ \text{globalMax} = \max(\text{globalMax}, \ \text{currentMax}) \]

初始时 currentMax = colSum[0], globalMax = colSum[0]，然后从 j=1 遍历到 j=n-1。

步骤3：组合所有行区间
我们需要枚举所有可能的 (rowStart, rowEnd) 组合。

• 外层循环：rowStart 从 0 到 m-1。
• 内层循环：rowEnd 从 rowStart 到 m-1。
  对于每一对 (rowStart, rowEnd)，我们都要：
  1. 计算 colSum 数组（可以动态更新，避免重复计算）。
  2. 对 colSum 运行 Kadane 算法得到当前行区间下的最大子矩阵和。
  3. 更新全局最大值。

计算 colSum 的高效方法：当 rowEnd 增加时，我们只需将第 rowEnd 行的各列值加到已有的 colSum 上即可，无需从 rowStart 开始重新累加。

步骤4：复杂度分析

• 枚举行区间：O(m²) 对组合。
• 对每个行区间，计算 colSum 并运行 Kadane 算法：O(n)。
• 总时间复杂度：O(m² × n)。当 m 和 n 同数量级时，约为 O(n³)。
• 空间复杂度：O(n)（用于存储 colSum 数组）。

示例推演
以前面给的 4×5 矩阵为例，演示部分过程：

1. 设 rowStart=1（第2行），rowEnd=1：
   colSum = 第2行本身 = [-8, -3, 4, 2, 1]
   Kadane 得到最大子数组和 = 4+2+1 = 7（对应子矩阵为第2行的第3~5列）。
2. 然后 rowEnd 增加到 2：
   colSum 加上第3行 → [-5, 5, 14, 3, 4]
   Kadane 得到最大和 = 整个数组和 21（对应子矩阵为第2~3行的所有列）。
3. 继续 rowEnd 增加到 3：
   colSum 加上第4行 → [-9, 4, 15, 10, -2]
   Kadane 得到最大和 = 4+15+10 = 29（对应子矩阵为第2~4行、第2~4列）。
   此时更新全局最大值为 29。
4. 继续枚举其他 rowStart，最终得到全局最大值 29。

边界情况

• 矩阵全为负数：最大子矩阵就是绝对值最小的那个负数（即最大元素自身）。Kadane 算法能正确处理。
• 矩阵只有一行：退化为最大子数组和问题。
• 矩阵只有一列：同样退化为最大子数组和（按行累加后只有一列，Kadane 仍然适用）。

关键点

• 核心技巧是“压缩行” + “Kadane算法”。
• 通过动态更新 colSum 避免重复累加，是优化到 O(m²n) 的关键。
• 这个方法是二维最大子矩阵问题的经典区间DP思路（虽然DP不明显，但本质是枚举区间并利用一维DP）。