arrays - 矩形子数组的最大和

Question

给定一个实数值数组，A[1..n,1..n] , 我希望找到子数组

B = A[i..j,s..t]

与 1 <= i <= j <= n,和 1 <= s <= t <= n

使得 B 中的数字之和被最大化。是否可以使用动态规划来解决这个问题？我与奥胡斯大学的一位 OR 教授交谈，他不知道该怎么做，并说他很难看到它如何具有最佳的子结构质量。

但这可能吗？如果是，如何？如果不是，为什么？

我已经知道在 O(n^3) 中运行的算法时间，将其减少到 n(n+1)/2复杂性的子问题 O(n) ，但这似乎有点慢。我知道最佳算法将在 Omega(n) 中运行时间，但我希望可以使用动态编程使其在 O(n^2) 中运行时间。

原始问题总结

我添加这一部分是因为我觉得有些人误解了我的问题。原来的问题是:

1. 是否可以使用动态规划来解决O(n^2)中的上述问题？时间？如果是，如何？如果没有，为什么不呢？

其他问题:

我在这里添加了一个新问题。以后可能会添加更多内容:

1. 为了使用动态规划，我需要使用解决方案来轻松解决子问题(否则这一点没有实际意义)。问题的结构是这样的，如果我们取一个子数组 B = A[1..m,1..m]的 A[1..n,1..n]其中 m < n , 那么数组的最优解 B最多和A一样好，很简单，因为相同的解决方案在 A 中是可行的.因此，要使用动态规划，有理由问:A[1..i,1..i] 的最优子数组之间的关系是什么？和 A[1..i+1,1..i+1] 的最优子数组？

Answer 1

一个可能有用的优化是在您可以计算出分数不可能超过当前最佳分数时跳过检查 a,b 对。

例如，一种方法是:

1. 在每一行上运行 Kadane 算法(n 次重复 O(n) 算法 = O(n^2))并将最大值存储在数组 M 中。
2. 在O(n)时间内计算数组M的垂直前缀和
3. 现在对于每个 a,b 对，我们可以使用我们的垂直前缀和来获得可以从此配对中获得的总和的上限，如果它低于我们当前的最佳值，则跳过测试。

如果您还在数组 M 上运行 Kadane 的算法并首先测试生成的 a,b 对，这可能效果最好。

在最好的情况下(例如，图像包含黑色背景和内部某处的白色矩形)这将在 O(n^2) 中找到答案，但对于更复杂的输入，它仍然需要 O(n^3) .

警告:在实践中，这个技巧可能只会对非常小的输入集有帮助，代价是会减慢大多数...

编辑:一些额外的解释:

对于第 i 行，M[i] 包含可以从 A[i..i,x..y] 形式的任何高度为 1 的矩形中获得的最大值。

我们定义了一个新的数组P[i](在上面的描述中称为垂直前缀和)。

P[0]=0
P[i+1]=M[i]+P[i]

对于行 s 和 t 的给定选择，我们可以通过计算 sum(M[ i] for i in range(s,t+1)).这实际上为我们提供了类似形状的值:

...           Row s
 ....
 .......
   ....       Row t

从 s 和 t 之间的每一行中取最佳高度 1 的矩形形成。

数组 P[i] 很有用，因为 P[i] = sum(M[j] for j in range(i))，所以我们可以计算 sum(M[i] for i in range(s,t) +1)) = P[t+1]-P[s] 在 O(1) 时间内。