

Subject:
Maximum difference Algorithm
Category: Computers > Algorithms Asked by: semsem66ga 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 = max1i,jn {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 bigO notation. 

There is no answer at this time. 

Subject:
Re: Maximum difference Algorithm
From: jamesjacksonga 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] endif if a[i] < small then small = a[i] endif endfor return big  small Complexity is O(n). 
Subject:
Re: Maximum difference Algorithm
From: frdega 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: kozlega 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.fhflensburg.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: bighugegamerga on 28 Oct 2005 13:35 PDT 
//simple : //parse array for smallest number //parse for largest number //compute difference //complexity O(n) // #include <iostream> 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<<endl<<"Max Difference is : "<<M<<" between numbers at positions : "<<x<<"("<<A[x]<<")"<<" and "<<y<<"("<<A[y]<<")"<<endl; } int getMaxDiff (int A[], int n,int &x, int &y) { int i; int small, big; small=big=A[0]; x=y=0; for (i=0; i<n;i++) { if (A[i]<small) {small=A[i]; x=i;} else { if (A[i]>big) {big=A[i]; y=i;} } } return (bigsmall); } 
Subject:
Re: Optimal Algorithm
From: meranaamxpertga 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 2n2 no. of comparisions in the worst case. I will give a 1.5n2 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[n1] (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/22 no. of comparisions with still O(n) complexity This is the BEST and OPTIMAL algorithm one can get for all kinds of inputs 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 