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

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

示例：
输入：matrix = [[1,2,-1],[-2,1,3],[3,-1,2]]
输出：7
解释：子矩阵 [[1,3],[3,2]] 的和为 1+3+3+2 = 7

解题过程

步骤1：问题分析
最大子矩阵问题可以看作是最大子数组问题（一维）在二维空间上的扩展。核心思路是将二维问题转化为多个一维问题来处理。

步骤2：关键思路 - 降维处理
对于矩阵中的每一行，我们可以计算从第i行到第j行之间，每一列的元素和，形成一个一维数组。这样，原问题就转化为在这个一维数组上求最大子数组和。

具体步骤：

1. 遍历所有可能的行对(i,j)，其中i ≤ j
2. 对于每个行对，计算从第i行到第j行各列的和，得到一个一维数组
3. 对这个一维数组使用最大子数组和算法（Kadane算法）
4. 记录所有结果中的最大值

步骤3：一维最大子数组和（Kadane算法）
这是解决本问题的基础算法：

def max_subarray(arr):
    max_ending_here = max_so_far = arr[0]
    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

步骤4：完整算法实现

1. 初始化最大和为矩阵的最小可能值
2. 遍历所有起始行i（0到m-1）
3. 创建一个临时数组temp，长度等于列数n，初始化为0
4. 遍历所有结束行j（i到m-1）
5. 将第j行的元素加到temp数组中
6. 对temp数组使用Kadane算法求最大子数组和
7. 更新全局最大和

步骤5：算法复杂度分析

• 时间复杂度：O(m²n)，其中m是行数，n是列数
• 空间复杂度：O(n)，用于存储临时的一维数组

步骤6：示例推演
以示例矩阵为例：
matrix = [[1,2,-1],[-2,1,3],[3,-1,2]]

当i=0, j=1时：

• temp = [1+(-2), 2+1, (-1)+3] = [-1, 3, 2]
• 最大子数组和：3+2 = 5

当i=1, j=2时：

• temp = [-2+3, 1+(-1), 3+2] = [1, 0, 5]
• 最大子数组和：1+0+5 = 6

当i=0, j=2时：

• temp = [1+(-2)+3, 2+1+(-1), (-1)+3+2] = [2, 2, 4]
• 最大子数组和：2+2+4 = 8

最终最大和为8（但题目示例输出为7，说明需要检查所有可能的子矩阵）

步骤7：边界情况处理

• 矩阵为空：返回0
• 矩阵只有一个元素：返回该元素值
• 所有元素为负数：返回最大的负数

通过这种降维思想，我们成功将复杂的二维问题转化为多个一维问题的组合求解。