寻找总和最大的子矩阵

Question

可能的重复：
查找最大可能总和为 O(n) 的子矩阵^2)

我有一个 NxN 矩阵。我想找出上述矩阵的一个 MxM 子矩阵，其元素之和最大。

什么是有效的算法？

Answer 1

我有一个算法，在放大 M 时以恒定时间运行，在放大 N 时以二次时间运行。

第一个子矩阵照常计数。存下这笔钱。然后向右移动一行字段 - 两个 MxM 矩阵重叠，因此您只需将两个不重叠的列相加即可。把所有的钱都存起来。现在您可以选择该行的最大总和。

移至下一行。还记得节省的金额吗？第一行和第二行的 MxM 矩阵再次重叠，因此您可以将 MxM 矩阵的第一行和最后一行相加，并计算第二行中的第一个总和。

现在转到第二行的第二个和。执行与上面相同的操作，但您会发现第二行中第一个 sum 和第二个 sum 的最后一行再次重叠。

我知道这有点令人困惑，如果你不明白，请告诉我，我会画一些图。该算法基于 这个答案。

编辑：我知道我承诺过图片，但这应该足够了：

A  AB   AB   AB   AB   B
AC ABCD ABCD ABCD ABCD BD
AC ABCD ABCD ABCD ABCD BD
AC ABCD ABCD ABCD ABCD BD
AC ABCD ABCD ABCD ABCD BD
 C   CD   CD   CD   CD  D

这是四个子矩阵，A、B、C、D，定位如下：

AB
CD

首先计算 A 子矩阵的总和：sum(A)。这里没有优化。现在您想要计算 B 的总和：sum(B)。您可以执行与 A 中相同的操作，但请注意 A 和 B 重叠。因此，您将 sum(A) 分配给 sum(B)，计算垂直向量 A AC AC AC AC 的总和，并从 sum(B) 中减去 if，然后计算垂直向量 的总和B BD BD BD BD 并将其添加到 sum(B)。

sum(B) = sum(A) - sum(A AC AC AC AC) + sum(B BD BD BD BD)

你有总和(B)。现在您可以继续计算整个第一行 submatices。

移至第二行：matices C 和 D。您不必对整个 matice C 求和，因为在上一行中，您保存了 sum(A)。注意它们再次重叠。您只需添加 A 和 C 之间的差：

//code (1)
subC = sum([A AB AB AB AB])   //as substract C
addC = sum([C CD CD CD CD])   //as add C
sum(C) = sum(A) - subC + addC

您就得到了 sum(C)。现在你可以像这样得到 sum(D)：

//code (2)
subD = sum([AB AB AB AB B])    //as substract D
addD = sum([CD CD CD CD D])    //as add D
sum(D) = sum(B) - subD + addD 

但是比较 subD 与 subC 以及 addD 与 addC。它们重叠！所以你可以这样做：

//code (3)
subD = subC - A + B //from subC substract value on A and add B to it
addD = addC - C + D //same as above
sum(D) = sum(B) - subD + addD

你会看到，我们不是对一个子矩阵的计算和进行 25 次添加，而是进行 6 次添加。对于 MxM 的每种可能大小，我们对第一个子矩阵进行 MxM 次添加，对第一行进行 M*2+2 次添加以及第一列和其余 6 个附加项。