**A pair contains two numbers, and its second number is on the right side of the first one in an array. The difference of a pair is the minus result while subtracting the second number from the first one. Please implement a function which gets the maximal difference of all pairs in an array. For example, the maximal difference in the array {2, 4, 1, 16, 7, 5, 11, 9} is 11, which is the minus result of pair (16, 5).**

__Problem:__**A naïve solution with brute force is quite straightforward: We can get the result for each number minus every number on its right side, and then get the maximal difference after comparisons. Since O(n) minus operations are required for each number in an array with n numbers, the overall time complexity is O(n**

__Analysis:__^{2}). Brutal force solution usually is not the best solution. Let us try to reduce the times of minus operations.

*Solution 1: via divide and conquer*
We divide an array into two sub-arrays with same size. The
maximal difference of all pairs occurs in one of the three following
situations: (1) two numbers of a pair are both in the first sub-array; (2) two
numbers of a pair are both in the second sub-array; (3) the minuend is in the
greatest number in the first sub-array, and the subtrahend is the least number
in the second sub-array.

It is not a difficult to get the maximal number in the first
sub-array and the minimal number in the second sub-array. How about to get the
maximal difference of all pairs in two sub-arrays? They are actually
sub-problems of the original problem, and we can solve them via recursion. The
following are the sample code of this solution:

int
MaxDiff_Solution1(int numbers[], unsigned length)

{

if(numbers
== NULL || length < 2)

return
0;

int max,
min;

return
MaxDiffCore(numbers, numbers + length - 1, &max, &min);

}

int
MaxDiffCore(int* start, int* end, int* max, int* min)

{

if(end ==
start)

{

*max = *min = *start;

return
0x80000000;

}

int* middle
= start + (end - start) / 2;

int
maxLeft, minLeft;

int
leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);

int
maxRight, minRight;

int
rightDiff = MaxDiffCore(middle + 1, end, &maxRight, &minRight);

int
crossDiff = maxLeft - minRight;

*max = (maxLeft > maxRight) ? maxLeft :
maxRight;

*min = (minLeft < minRight) ? minLeft :
minRight;

int maxDiff
= (leftDiff > rightDiff) ? leftDiff : rightDiff;

maxDiff = (maxDiff > crossDiff) ?
maxDiff : crossDiff;

return
maxDiff;

}

In the function MaxDiffCore,
we get the maximal difference of pairs in the first sub-array (leftDiff), and then get the maximal
difference of pairs in the second sub-array (rightDiff).
We continue to calculate the difference between the maximum in the first
sub-array and the minimal number in the second sub-array (crossDiff). The greatest value of the
three differences is the maximal difference of the whole array.

We can get the minimal and maximal numbers, as well as their
difference in O(1) time, based on the result of two sub-arrays, so the time
complexity of the recursive solution is T(n)=2(n/2)+O(1). We can demonstrate
its time complexity is O(n).

*Solution 2: get the maximum numbers while scanning*
Let us define diff[i] for the difference of a pair whose subtrahend
is the i

^{th}number in an array. The minuend corresponding to the maximal diff[i] should be the maximum of all numbers on the left side of i^{th}number in an array. We can get the maximal numbers on the left side of each i^{th}number in an array while scanning the array once, and subtract the i^{th}number for them. The following code is based on this solution:
int
MaxDiff_Solution3(int numbers[], unsigned length)

{

if(numbers
== NULL || length < 2)

return 0;

int max =
numbers[0];

int maxDiff
= max - numbers[1];

for(int i = 2;
i < length; ++i)

{

if(numbers[i
- 1] > max)

max = numbers[i - 1];

int
currentDiff = max - numbers[i];

if(currentDiff
> maxDiff)

maxDiff = currentDiff;

}

return maxDiff;

}

It is obviously that its time complexity is O(n) since it is
only necessary to scan an array with length n once. It is more efficient than
the first solution on memory requirement, which requires O(

*log*n) memory for call stack for the recursion.The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going
to use part of or the whole of this ariticle in your blog
or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.