获取最大子矩阵的坐标
Get the coordinates of the largest submatrix
我有一个子矩阵m x n的最大子矩阵m1 x n1。我找到了最大子矩阵总和，但我想知道如何找到 r1c1（该子矩阵的第一行和第一列）和 r2c2（该子矩阵的最后一行和最后一列）的坐标。
到目前为止，我已经对矩阵进行了预处理，该矩阵将其总和存储在每个元素中，如：
SUM[i, j] = SUM[i−1, j] + SUM[i, j−1] − SUM[i−1, i−1] + MATRIX[i, j]
我发现对于任何给定的 r1、c1、r2、c2：
SUMS = SUM[r2,c2] - SUM[r1-1,c2] - SUM[r2,s1-1] + SUM[r1-1,c2-1]
如果我想得到可以告诉我这个子矩阵坐标的输出，我应该如何处理这个问题？
你可以暴力破解所有可能的 r1 和 r2，然后你可以再次暴力破解所有可能的 c1 和 c2 这对 r1, r2并通过 SUM 数组计算此子矩阵的总和，这很简单，但效率不高。
时间复杂度O(m2n2)
让我们尝试改进它。通过一些预处理，你可以在 O(1) 时间内知道每一列的 r1 到 r2 的总和。这样，我们将二维最大子矩阵问题转化为一维 Maximum Subarray Problem，这可以帮助我们在 O(n) 时间内找到此 r1, r2 对的 c1 和 c2 .
时间复杂度O(mn2)
我有一个子矩阵m x n的最大子矩阵m1 x n1。我找到了最大子矩阵总和，但我想知道如何找到 r1c1（该子矩阵的第一行和第一列）和 r2c2（该子矩阵的最后一行和最后一列）的坐标。
到目前为止，我已经对矩阵进行了预处理，该矩阵将其总和存储在每个元素中，如：
SUM[i, j] = SUM[i−1, j] + SUM[i, j−1] − SUM[i−1, i−1] + MATRIX[i, j]
我发现对于任何给定的 r1、c1、r2、c2：
SUMS = SUM[r2,c2] - SUM[r1-1,c2] - SUM[r2,s1-1] + SUM[r1-1,c2-1]
如果我想得到可以告诉我这个子矩阵坐标的输出，我应该如何处理这个问题？
你可以暴力破解所有可能的 r1 和 r2，然后你可以再次暴力破解所有可能的 c1 和 c2 这对 r1, r2并通过 SUM 数组计算此子矩阵的总和，这很简单，但效率不高。
时间复杂度O(m2n2)
让我们尝试改进它。通过一些预处理，你可以在 O(1) 时间内知道每一列的 r1 到 r2 的总和。这样，我们将二维最大子矩阵问题转化为一维 Maximum Subarray Problem，这可以帮助我们在 O(n) 时间内找到此 r1, r2 对的 c1 和 c2 .