**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.

if Max is left to the Min, get max of the following three sections

ReplyDelete1. Max - min(right to Max),

2. MaxDiff of Max+1 to Min-1

3. max(left to Min)- Min

Check this for c# interview questions @ http://skillgun.com

ReplyDeleteCan this problem be solved using dynamic programming ?

ReplyDeletefor each index i, find the largest number that lies before it. and it can be done by the following formula.

f(i) = the largest number that lies before i

f(i) = f(i-1) if a[i-1] < f(i-1)

else f(i) = a[i-1] if a[i-1] >= f(i-1)

Kindly reply.

--

Sandeep Singh

I write below program. Check it and give your feedback .

ReplyDeletepublic Pair findMaxPair(int inputArray[])

{

int index = 0 ,len =inputArray.length,firstElm=-1, secondElm=-1;

int curElement=0, first=-1,second=-1;

for(;index first)

{

first =curElement;

}else if(curElement (firstElm-secondElm))

{

firstElm=first;

secondElm = second;

}

}

}

return new Pair(firstElm,secondElm);

}

}

class Pair

{

int first;

int second;

public Pair(int first, int second) {

// TODO Auto-generated constructor stub

this.first=first;

this.second=second;

}

int difference ()

{

return first-second;

}

public String toString()

{

return "( "+first+", "+ second+"):diff:"+(first-second);

}

}

Time complexity is O(n). I am traversing array just once. Here i created Pair Class to return.

ReplyDeleteto Harry He

ReplyDeleteMay be I don't understand question but:

1. If we talk about that the maximum difference must be negative, i.e. second number must be greater than first number. Then for input {2, 4, 3} MaxDiff_Solution3 output will be {4, 3} = 1 (if we do not take into account the sign), and it's ok, but then for input { 2, 4, 5 } it must output 0 (max negative difference not found), but its output is {4, 5} = -1.

2. If we talk about that the maximum difference (does not matter positive or negative), then MaxDiff_Solution3 for input {2, 4, 3} and for { 2, 4, 5 }, must output {2, 4} = 2.

I will be grateful for the answer.