含左上角单元格的二维最大子矩阵问题能否以O(nm)时间高效求解？

结论 #

可以在O(nm)时间复杂度内求解包含矩阵左上角单元格的最大和子矩阵，同时得到子矩阵本身。

核心思路 #

所有包含左上角(0,0)的子矩阵，必然是以(0,0)为左上角、右下角为(i,j)（0≤i<n，0≤j<m）的矩形（因为子矩阵必须覆盖(0,0)，而矩阵索引非负，所以子矩阵的左上角只能是(0,0)）。我们可以通过二维前缀和的方式，遍历所有这类矩形，计算它们的和并记录最大值及对应右下角坐标，最终提取出最优子矩阵。

具体实现步骤 #

1. 初始化：将初始最大和设为左上角元素的值，最优子矩阵的右下角坐标设为(0,0)。
2. 处理第一行：计算每个位置的前缀和（当前元素+左侧前缀和），若当前和大于记录的最大和，则更新最大和及右下角坐标。
3. 处理第一列：计算每个位置的前缀和（当前元素+上方前缀和），同理更新最大和及坐标。
4. 处理其余位置：使用二维前缀和公式避免重复计算：

   dp[i][j] = matrix[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
   

   每次计算后更新最大和及对应右下角坐标。
5. 提取子矩阵：根据记录的右下角坐标(r,c)，从原矩阵中提取从(0,0)到(r,c)的子矩阵。

代码示例（Python） #

def max_submatrix_with_top_left(matrix):
    if not matrix or not matrix[0]:
        return [], 0
    
    n, m = len(matrix), len(matrix[0])
    original = [row.copy() for row in matrix]
    dp = [row.copy() for row in matrix]
    
    max_sum = dp[0][0]
    bottom_right = (0, 0)
    
    # 处理第一行
    for j in range(1, m):
        dp[0][j] += dp[0][j-1]
        if dp[0][j] > max_sum:
            max_sum = dp[0][j]
            bottom_right = (0, j)
    
    # 处理第一列
    for i in range(1, n):
        dp[i][0] += dp[i-1][0]
        if dp[i][0] > max_sum:
            max_sum = dp[i][0]
            bottom_right = (i, 0)
    
    # 处理其余位置
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            if dp[i][j] > max_sum:
                max_sum = dp[i][j]
                bottom_right = (i, j)
    
    # 提取最优子矩阵
    r, c = bottom_right
    submatrix = [original[i][:c+1] for i in range(r+1)]
    
    return submatrix, max_sum

# 测试示例
matrix = [
    [1, -2, 3],
    [4, -5, 6],
    [-7, 8, -9]
]
submatrix, sum_val = max_submatrix_with_top_left(matrix)
print("最大和:", sum_val)
print("最优子矩阵:")
for row in submatrix:
    print(row)

复杂度分析 #

• 时间复杂度：O(nm)，每个元素仅被访问和计算一次。
• 空间复杂度：O(nm)，用于存储原矩阵副本和dp数组（可优化为O(1)，直接在原矩阵上修改，但会破坏原矩阵数据）。

内容的提问来源于stack exchange，提问作者Simd