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.

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

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'

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

//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);
	
}

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