algorithm - 非常特殊矩阵的最大子矩形

Question

在处理图像处理任务时，我遇到了以下问题:单位正方形中有 n 个点，坐标为 $x_i$ 和 $y_i$，每个点都分配有正或负权重 $w_i$。找到一个矩形，使得位于该矩形内的那些点的所有权重之和为正且最大。

通过定义适当的网格，问题可以改写为在 n×n 矩阵 A 中找到元素和最大的子矩阵。这也称为“最大子矩形问题”，之前已在 SO 上讨论过。虽然蛮力方法的运行时间为 O(n^5)，但有一种复杂的解决方案的运行时间为 O(n^3)。它利用了相应的一维问题的解决方案，称为 "maximal subarray problem" , 运行时间为 O(n)。

我已经在 R 中实现了这两种算法，可以在几秒钟内解决 100 多个点。但是如果有数千个点，它就会太慢，即使将循环外包给某些 Fortran 或 C 代码也可能如此。

现在看一下矩阵 A。当假设(不失一般性)所有点都有不同的 x 或 y 坐标时，A 有一个特殊的形式:在 A 的每一行和每一列中，恰好有 一个非零元素。对于具有这种特殊属性的矩阵，我认为应该有一种算法可以在 O(n^2) 时间内完成任务，甚至更好。

这是添加了最佳矩形的示例:

set.seed(723)
N <- 50; w <- rnorm(N)
x <- runif(N); y <- runif(N)
clr <- ifelse (w >= 0, "blue", "red")
plot(x, y, pch = 20, col = clr, xlim = c(0, 1), ylim = c(0, 1))
rect(0.075, 0.45, 0.31, 0.95, border="gray")

你看可以有红色，即。负值，指向最佳矩形。它还表明，解决 x 和 y 坐标的一维情况是不够的。

我会将标准解决方案翻译成 Fortran，但我当然希望手头有一个更高效的算法。

Answer 1

These guys (从维基页面找到)声称对二维情况有一个更简单的子立方解决方案。它可能是您已经知道的那个。