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

Question

Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].

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

Examples:

• If array is [2, 3, 10, 6, 4, 8, 1, 7] then returned value should be 8 (Diff between 10 and 2).

• If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9)

My Algorithm:

I thought of using D&C algorithm. Explanation

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

Here as these elements will remain in same order, i will get the maximum difference, here it's 6.

Now i will move back to merege these arrays and again find the difference between minimum of first block and maximum of second block and keep doing this till end.

I am not able to implement this in my code. can anyone please provide a pseudo code for this?

Answer 1

We have max { A[i] - A[j] | i > j } = max { A[i] - min { A[j] | j < i } | i }, which yields a straightforward O(n) algorithm:

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 is conceptionally more complicated, but also leads to a linear time solution (with a higher constant factor).