c++ - 寻找总和最大的子矩阵

Question

<分区>

Answer 1

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

第一个子矩阵照常计数。保存总和。然后向右移动一个行字段 - 两个 MxM 矩阵重叠，因此您可以只对两个不重叠的列求和。保存所有金额。现在您可以为该行选择最大的总和。

移动到下一行。还记得节省的金额吗？第一行和第二行的 MxM 矩阵再次重叠，因此您可以只对第一行和最后一行 MxM 矩阵求和，然后在第二行计算第一个和。

现在转到第二行的第二个总和。同上，但是你发现第二行的first sum和second sum的最后一行又重叠了。

我知道这有点令人困惑，如果你不明白，让我知道我会画一些图。该算法基于论文 this answer .

编辑:我知道我答应了图片，但这应该足够了:

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)，计算垂直 vector 的总和 A AC AC AC AC 并从 sum(B) 中减去 if，然后计算垂直 vector 的总和 B BD BD BD BD 并将其添加到 sum(B)。

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

你有 sum(B)。现在您可以继续计算整个第一行子矩阵。

移至第二行:矩阵 C 和 D。您不必对整个矩阵 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 个补充。