在矩阵中寻找最大子矩形和

Question

给定一个由正数和负数整数组成的二维数组，找到具有最大和的子矩阵。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩阵被称为最大子矩阵。子矩阵是指整个数组中大小为1*1或更大的任何连续子数组。例如，数组的最大子矩阵为：

可能重复：
获取最大和的子矩阵？

 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2

位于左下角：

 9  2
-4  1
-1  8

并且总和为15。

因此，给定一个矩形，找到最大子矩形的总和的有效算法是什么（在上面的例子中为15）。

- Raj

---

这听起来像是一道作业题。如果我替你完成它，我会得到金星贴纸吗？ - FrustratedWithFormsDesigner

肯定是一道作业题。 - Ruel

@FrustratedWithFormsDesigner：不是的，我上周在一个编程比赛中遇到了这个问题。我努力想弄清楚逻辑，但都徒劳无功。希望有人能给予一些启示... - Raj

@user441575：哦，好的。将来你可能想引用来源，这样人们就不会认为这是作业并更愿意帮助你（因为这个看起来像是直接从作业单上复制的）。 - FrustratedWithFormsDesigner

矩阵的最大尺寸是多少，Neo？ - Déjà vu

Answer 1

您可以使用 O(numCols*numLines^2) 的时间复杂度来解决此问题。考虑相同的一维问题：

给定一个由 n 个元素组成的向量，找到最大和的连续子序列。

令 S[i] = 以 i 结尾的最大和连续子序列。我们有 S[1] = array[1] 和 S[i > 1] = max(S[i - 1] + array[i], array[i])。

注意，您不需要向量来解决此问题，只需两个变量即可。更多信息请点击 这里。

现在，对于您的矩阵情况，请计算 Sum[i][j] = 列 j 的前 i 个元素之和。

现在，对于您矩阵中每一对可能的行，请将当前对的元素之间的“向量”应用于 1d 算法。

- IVlad

---

这个答案需要使用这个优秀的材料来完成：http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf - Alexandre C.