最大子矩阵

难度: Hard

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例：

输入：
[
   [-1,0],
   [0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵

说明：

1 <= matrix.length, matrix[0].length <= 200

Submission

运行时间: 936 ms

内存: 18.8 MB

class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        H, W, ans = len(matrix), len(matrix[0]), -sys.maxsize - 1
        prefixSum = [[0 for _ in range(W)] for _ in range(H + 1)]

        # 纵向前缀和
        for i in range(1, H + 1):
            for j in range(0, W):
                prefixSum[i][j] = prefixSum[i - 1][j] + matrix[i - 1][j]

        for top in range(H):
            for bottom in range(top, H):
                left = 0
                dp = -sys.maxsize - 1
                for right in range(W):
                    num = prefixSum[bottom + 1][right] - prefixSum[top][right]
                    if dp > 0:
                        dp += num
                    else:
                        dp = num
                        left = right
                    if dp > ans:
                        ans = dp
                        points = [top, left, bottom, right]
        return points

Explain

这个问题可以通过将二维问题转化为一维问题来解决。首先，我们通过计算矩阵的纵向前缀和来简化区间求和的操作。然后，通过固定子矩阵的上下界（top 和 bottom），将问题转换为求解固定行区间内部的最大子数组和，这一步使用类似Kadane算法的动态规划方法。对于每一对上下界，我们遍历所有可能的左右边界，计算这个矩形区间的和，并更新最大值。如果当前的累积和为负数，则重新开始计算新的子数组，否则继续累加。

时间复杂度: O(H^2 * W)

空间复杂度: O(H * W)

class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        H, W, ans = len(matrix), len(matrix[0]), -sys.maxsize - 1
        # 存储纵向前缀和
        prefixSum = [[0 for _ in range(W)] for _ in range(H + 1)]

        # 计算纵向前缀和
        for i in range(1, H + 1):
            for j in range(0, W):
                prefixSum[i][j] = prefixSum[i - 1][j] + matrix[i - 1][j]

        for top in range(H):
            for bottom in range(top, H):
                left = 0
                dp = -sys.maxsize - 1
                for right in range(W):
                    num = prefixSum[bottom + 1][right] - prefixSum[top][right]
                    if dp > 0:
                        dp += num
                    else:
                        dp = num
                        left = right
                    if dp > ans:
                        ans = dp
                        points = [top, left, bottom, right]
        return points

Explore

在解决最大子矩阵问题时，选择纵向前缀和而不是横向前缀和的原因主要是由于我们需要处理和优化对任意子矩阵的求和操作。通过固定子矩阵的上下界（即行），我们可以将二维问题降维到一维问题，即在固定的行范围内寻找最大的子数组和。如果我们使用纵向前缀和，可以非常便捷地通过两个前缀和之差直接得到任意两行间的列元素和，这样我们就可以将问题简化为求解一维数组的最大子数组和。如果使用横向前缀和，虽然也可以处理，但在固定行的情况下对列的处理会变得复杂，不如纵向前缀和直接和高效。

纵向前缀和数组的索引从1开始而不是0的设计是为了方便计算和处理边界情况。在计算过程中，我们需要通过前缀和数组快速获取从第一行到任意第i行的累积和。如果从1开始，我们可以非常方便地通过prefixSum[bottom + 1][column] - prefixSum[top][column]来计算从第top行到第bottom行的和。若从0开始，则每次计算时都需要做额外的判断或调整，以确保不越界或错误地引用了不存在的索引-1的元素。因此，从1开始可以简化代码逻辑，避免边界问题。

在Kadane算法中，当当前累积和变为负数时，重置累积和是基于这样的理念：一个负的累积和不会对求取最大子数组和产生帮助，因为任何包含这个负累积和部分的更大数组的总和都会比不包含这一部分的总和更小。因此，重置累积和并从下一个元素重新开始，不会错过最优解。这是算法确保能够找到最大子数组和的关键步骤，而不是一个可能导致漏解的问题点。