线性动态规划：最大子矩阵和问题

题目描述
给定一个 m x n 的整数矩阵 matrix，请找出其中元素和最大的子矩阵，返回该子矩阵的元素和。
例如，矩阵

\[\begin{bmatrix} 1 & 2 & -1 \\ -3 & -1 & 4 \\ 1 & -5 & 2 \end{bmatrix} \]

的最大子矩阵和为 6，对应子矩阵为

\[\begin{bmatrix} -1 & 4 \\ -5 & 2 \end{bmatrix} \]

中所有元素的和（-1 + 4 + (-5) + 2 = 0？这里需要纠正：实际最大子矩阵可能是整个第二列和第三列的部分组合，需通过计算验证。我们直接进入解法）。

解题过程

步骤1：将二维问题转化为一维问题
最大子矩阵和问题可以转化为多个一维的“最大子数组和”问题。具体思路是：

• 枚举矩阵的上下边界（即子矩阵的顶部行和底部行），将这两行之间的每一列压缩成一个一维数组。
• 对每个压缩后的一维数组，使用 Kadane 算法求最大子数组和。
• 所有上下边界组合中，最大的那个和就是答案。

步骤2：列压缩方法
设矩阵有 m 行 n 列。对于上下边界 top（从 0 到 m-1）和 bottom（从 top 到 m-1），我们计算一个压缩数组 colSum[0..n-1]：

\[colSum[j] = \sum_{i=top}^{bottom} matrix[i][j] \]

这样，colSum[j] 表示第 j 列从 top 行到 bottom 行的元素和。

步骤3：对压缩数组应用 Kadane 算法
Kadane 算法求最大子数组和：

• 设 dp[i] 表示以第 i 个元素结尾的最大子数组和。
• 状态转移：dp[i] = max(colSum[i], dp[i-1] + colSum[i])
• 最大子数组和 = max(dp[0..n-1])

步骤4：枚举所有上下边界
对每个 top 从 0 到 m-1：

• 初始化一个长度为 n 的数组 temp，初始为 0。
• 对每个 bottom 从 top 到 m-1：
  • 更新 temp[j] += matrix[bottom][j]（即累加当前 bottom 行到 temp 中）
  • 对 temp 数组执行 Kadane 算法，得到当前上下边界下的最大子矩阵和。
• 更新全局最大和。

步骤5：时间复杂度
枚举上下边界 O(m²)，每次 Kadane 算法 O(n)，总复杂度 O(m²n)。若 m > n，可转置矩阵使 O(min(m,n)² * max(m,n))。

举例说明
矩阵：

\[\begin{bmatrix} 1 & 2 & -1 \\ -3 & -1 & 4 \\ 1 & -5 & 2 \end{bmatrix} \]

1. top=0, bottom=0：压缩数组 [1, 2, -1]，Kadane 得最大和 3（子数组 [1,2]）
2. top=0, bottom=1：压缩数组 [1+(-3)= -2, 2+(-1)=1, -1+4=3]，Kadane 得最大和 4（子数组 [1,3] 或 [3]？实际计算：dp[0]=-2, dp[1]=max(1, -2+1)=1, dp[2]=max(3,1+3)=4，最大和 4）
3. top=0, bottom=2：压缩数组 [1-3+1=-1, 2-1-5=-4, -1+4+2=5]，Kadane 得最大和 5（子数组 [5]）
4. top=1, bottom=1：压缩数组 [-3, -1, 4]，最大和 4
5. top=1, bottom=2：压缩数组 [-3+1=-2, -1-5=-6, 4+2=6]，最大和 6
6. top=2, bottom=2：压缩数组 [1, -5, 2]，最大和 2（子数组 [1,2] 或 [2]？实际 [1,2] 和=3）
   全局最大和是 max(3,4,5,4,6,3) = 6。

对应子矩阵是 top=1, bottom=2, j=2 到 j=2（即最后一列）？不对，因为 j=2 单独和为 6？检查：第1行第2列=4，第2行第2列=2，和=6。但也可以跨列？这里 Kadane 在 top=1,bottom=2 时压缩数组为 [-2, -6, 6]，最大子数组是 [6] 单独一个元素，所以子矩阵是右下角的 2x1 矩阵 [4; 2]？但 4+2=6 正确。实际上最大子矩阵是整个最后两列？不对，因为中间有负数。最终结果是 6。

代码框架（伪代码）

maxSum = -∞
for top = 0 to m-1:
    temp = [0] * n   # 压缩数组
    for bottom = top to m-1:
        for j = 0 to n-1:
            temp[j] += matrix[bottom][j]
        # 对 temp 用 Kadane 算法
        curMax = temp[0]
        dp = temp[0]
        for j = 1 to n-1:
            dp = max(temp[j], dp + temp[j])
            curMax = max(curMax, dp)
        maxSum = max(maxSum, curMax)
return maxSum

这样，我们通过将二维问题转化为多个一维最大子数组和问题，解决了最大子矩阵和问题。