划分和征服Algo以找到两个有序元素之间的最大差异

Question

给定一个整数的数组arr [],找出任何两个元素之间的差异,使得较大的元素出现在arr []中较小的数字之后.

Max Difference = Max { arr[x] - arr[y] | x > y }

例子:

• 如果[2, 3, 10, 6, 4, 8, 1, 7]返回数组,则值应为8(10和2之间的差值).

• 如果[ 7, 9, 5, 6, 3, 2 ]返回数组,则值应为2(7到9之间的差异)

我的算法:

我想过使用D&C算法.说明

2, 3, 10, 6, 4, 8, 1, 7

then

2,3,10,6      and     4,8,1,7

then

2,3  and 10,6  and  4,8 and 1,7

then

2 and 3   10 and 6   4 and 8    1 and 7

在这里,因为这些元素将保持相同的顺序,我将得到最大的差异,这里是6.

现在我将回到merege这些数组并再次找到第一个块的最小值和第二个块的最大值之间的差异,并继续这样做直到结束.

我无法在我的代码中实现这一点.任何人都可以为此提供伪代码吗？

Answer 1

我们有max { A[i] - A[j] | i > j } = max { A[i] - min { A[j] | j < i } | i },它产生一个简单的O(n)算法:

prefix_min = A[0]
result = -infinity
for i := 1 to n - 1:
    # invariant: We have prefix_min = min { A[j] | j < i }
    result = max(result, A[i] - prefix_min)
    prefix_min = min(prefix_min, A[i])

Divide&Conquer在概念上更复杂,但也导致线性时间解决方案(具有更高的常数因子).