Google Answers Logo
View Question
 
Q: Maximum difference Algorithm ( No Answer,   5 Comments )
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 = 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 big-O notation.
Answer  
There is no answer at this time.

Comments  
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 <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 (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

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy