分裂与征服求二维数组中两个有序元素的最大差

Question

我现在使用分而治之算法在二维数组中查找两个有序元素之间的最大差异(这意味着Ai k>i和l>j中的−Ak )，如下所示：

0，3，6，4

9、3、1、6

7、8、5、6

1，2，3，4

结果是A1−A=8-0=8(不是A−A=9-0= 9 )。

最主要的问题是在一个一维数组中，如下所示：

Divide and Conquer Algo to find maximum difference between two ordered elements

那么，如何通过分治算法在二维阵列中求解呢？

非常感谢!

Answer 1

有一个直接的O(n^2)解决方案。为了计算A[i][j] − A[k][l]的最大值，现在让我们修复A[k][l]。假设下图中的A[k][l] = x。然后A[i][j]的候选集是阴影矩形。

因此，为了使A[i][j] − x最大。我们需要知道阴影面积的最大值，这可以通过简单的动态规划来计算。

+------+------+------+-----+
|      |      |      |     |
|      |      |      |     |
|      |      |      |     |
+--------------------------+
|      |      |      |     |
|      |  x   |      |     |
|      |      |      |     |
+--------------------------+
|      |      |------------|
|      |      |------------|
|      |      |------------|
+--------------------------|
|      |      |------------|
|      |      |------------|
|      |      |------------|
+------+-------------------+

定义

• area(i, j) = { A[x][y] | x > i, y > j }
• f(i, j) = max( area(i, j) )
• g(m, n) = max { f(i, j) - A[i][j] | 1 <= i <= m, 1 <= j <= n }

对于m*n矩阵，我们想要的是f(m, n)。

和f(i, j) = max { f(i+1, j), f(i, j+1), A[i][j] }

所以2 for循环应该完成这项工作。