一个矩形子数组的最大总和

Question

一个矩形子数组的最大总和

5

给定一个实数数组A[1..n,1..n]，我希望找到子数组B = A[i..j,s..t]，其中 1 <= i <= j <= n，而且 1 <= s <= t <= n，使得B中数字的总和最大。能否使用动态规划来解决这个问题？我曾与奥胡斯大学的OR教授交流过，他不知道该如何解决，并表示很难看出它具有最优子结构特性。但是，是否可能？如果是，怎么做？如果不是，为什么？

我已经知道一种运行时间为O(n^3)的算法，通过将其缩减为O(n)复杂度的n(n+1)/2个子问题来解决，但这似乎有点慢。我知道最佳算法将以Ω(n)的时间运行，但我希望可以使用动态编程使其运行时间为O(n^2)。

- Undreren

4

哦，真令人兴奋。@izomorphius会在接下来的24小时内死去，让我们像可怜的费马一样焦虑数个世纪吗！我希望不会，但我担心他在挑战命运。我明天会回来看看。 - High Performance Mark

2

请参见https://dev59.com/E3E85IYBdhLWcg3wtV_1。 - Benjamin

3

@HighPerformanceMark 我当然希望不会在接下来的24小时内死去，但如果发生了这种情况，我会回来鬼魂缠身，直到一个聪明人编写了解决方案并让我的痛苦灵魂得到永久的安息。请确保内容准确无误、通顺易懂。 - Ivaylo Strandjev

3

@Undreren说：“我没有那种感觉，我只是担心izomorphius。” - High Performance Mark

2

@izomorphius：光明的一面是，你在回家路上的不时之需死亡现在对我们其他人来说将不再是那么麻烦了 ;) - Undreren

显示剩余7条评论

2个回答

1

来自The Algorithmist，如果你有一个n x n的数组，最好的时间复杂度是O(n^3)：

首先，对于所有列计算垂直前缀和（一个O(n^2)的算法）。
其次，假设最大子数组将在行a和行b之间（包括a和b）。只有O(n^2)个a、b对满足a < b。尝试每一个组合。
由于我们已经有了所有列的垂直前缀和，因此可以在O(1)的时间内计算出arr[a..b][c]列中元素的总和。这使我们可以将每个列的总和想象成跨越所有列的一维数组的单个元素（具有一行和n列的一维数组）。
有一个O(n)的算法可以计算一维数组的最大子数组，称为Kadane算法。
在每个a和b的组合内应用Kadane算法，总复杂度为O(n3)。

假设你有一个n行2列的数组，你可以将其降至O(n^2)。关键在于使用Kadane算法，如上所述。

- PengOne

1

实际上，O(n^3) 是一个紧密的上界有证明吗？ - Undreren

此外，这篇文章并没有什么帮助，因为它只是总结了我已经知道的O(n^3)算法。最后一节很琐碎。如果你固定一个维度，那么使用Kadane算法的1D数组数量就是显然恒定的。 - Undreren

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

可能有用的优化是在能够计算出得分无法超过当前最佳得分时跳过检查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的选择，我们可以通过计算范围内（s到t+1）元素M[i]的总和来快速估计形如A[s..t,x..y]的矩形中最大值。这实际上给出了类似以下形状的值：

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

从每一行中的高度最佳矩形组成，形成一个数组。

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