我有一个子矩阵m1 x n1
中最大的子矩阵m x n
。我找到了最大子矩阵的总和,但是我想知道如何在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]
如果我想获得可以告诉我该子矩阵的坐标的输出,应该如何解决这个问题?