View Question
 Question
 Subject: Maximum difference Algorithm Category: Computers > Algorithms Asked by: semsem66-ga List Price: \$2.50 Posted: 20 Oct 2005 12:32 PDT Expires: 19 Nov 2005 11:32 PST Question ID: 582714
 ```Let A[1],A[2], . . . ,A[n] be an array containing n positive integers. Describe an efficient algorithm to find the maximum difference between any two integers in the array. In other words, compute M = max1i,jn {A[i] ? A[j]}. What is the complexity of your algorithm? Explain. If you know the exact complexity write it. Otherwise, you may use the big-O notation.```
 There is no answer at this time.

 Subject: Re: Maximum difference Algorithm From: jamesjackson-ga on 20 Oct 2005 15:00 PDT
 ```Here's the algorithm: let big = a[1] let small = a[1] for i = 1 to n do if a[i] > big then big = a[i] end-if if a[i] < small then small = a[i] end-if end-for return big - small Complexity is O(n).```
 Subject: Re: Maximum difference Algorithm From: frde-ga on 21 Oct 2005 06:27 PDT
 ```Look for the highest and the lowest in one pass This might be a trick question, whether comparison and assignment is faster than comparison followed by comparison Normally JMP is a lot slower than moving one register into another - so the trick answer is ( in Pascal ) :- If A[L9] >= Max Then // Note: NOT: A[L9] > Max {assign rather than JMP} Max := A[L9] // Assign and get out - save a probable JMP Else If A[L9] < Min Then // worst case one JMP Min := A[L9]; Basically pointing out that JGE avoids the 'Else'```
 Subject: Re: Maximum difference Algorithm From: kozle-ga on 25 Oct 2005 03:22 PDT
 ```Hi! Lets say that we sort this array whith heapsort that has O(n log(n)). Then we calculate the difference between the first and the last value in array! So int min = 0; int max = 0; a = heapSort(a); min = a[1]; //first max = a[n]; //last diff = max - min; complexity of heapSort algorithm is O(n*log(n)), so complexity of your algorithm should be O(n * log(n))! More obout this algorithm: www.iti.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm or en.wikipedia.org/wiki/Heapsort You can get this algorithm for any programming language you want (c,java,pascal...)```
 Subject: Re: Maximum difference Algorithm From: bighugegamer-ga on 28 Oct 2005 13:35 PDT
 ```//simple : //parse array for smallest number //parse for largest number //compute difference //complexity O(n) //--------------------------------------- #include using namespace std; int getMaxDiff (int A[], int n,int &x, int &y); int main() { int A[]={412,222,3,435,52,6,73,85,94,130}; int M; int x,y; M=getMaxDiff(A,10,x,y); cout<big) {big=A[i]; y=i;} } } return (big-small); }```
 Subject: Re: Optimal Algorithm From: meranaamxpert-ga on 02 Jan 2006 20:24 PST
 ```I just give algo here which can be easily programmed! Most of the O(n) algorithms mentioned here do have 2n-2 no. of comparisions in the worst case. I will give a 1.5n-2 no. of comparisions algo here. 1) if a[0]>a[1] {tempMin = a[1]; tempMax=a[0];} else {tempMin = a[0]; tempMax=a[1];} 2) for every consecutive pair of elements from a[2] to a[n-1] (means a[2],a[3] and a[4],a[5] and a[6],a[7]..total .5n pairs) a) first compare a[i] and a[i+1] b) compare tempMin and min of above pair c) compare tempMax and max of above pair so like that 3 comparisions for every pair ==> 3n/2 no. of comparisions But first pair a[0],a[1] has only one comparision in step 1 so TOTAL 3n/2-2 no. of comparisions with still O(n) complexity This is the BEST and OPTIMAL algorithm one can get for all kinds of inputs```