CareerCup

Here is a O(n) solution.

curMin=MAX;
curMaxDiff=0;
for ele in array[0,n-1]
   if(ele < curMin)
       curMin=ele
   else if( (ele-curMin)>curMaxDiff )
       curMaxDiff=ele-curMin
end for
output curMaxDiff

Or take a better example, [ 7 9 5 6 3 2 ] Ans-> 2 [9 - 7]

There is a easy nsquare soln. Are you looking for to reduce the complexity?

Hi,
also we can solve by taking the smallest and biggest element in the array, and the max difference would be answer
O(n) solution

public void MaximumDifferenceBetweenTwoElements()
            {
                //The function assumes that there are at least two
                //elements in array.
                //The function returns a negative value if the array is
                //sorted in decreasing order.
                //Returns 0 if elements are equal


                //We take difference between the picked element and the minimum element found so far.
                //So we need to keep track of 2 things:
                //1) Maximum difference found so far (max_diff).
                //2) Minimum number visited so far (min_element).
                int [] arr = {2, 3, 10, 6, 4, 8, 1};
                
                int maxDiff = arr[1] - arr[0];
                int minElement = arr[0];
                for (int i = 1; i < arr.Length; i++)
                {
                    if (arr[i] - minElement > maxDiff)
                        maxDiff = arr[i] - minElement;
                    
                    if (arr[i] < minElement)
                        minElement = arr[i];
                }

                Console.WriteLine(maxDiff);
            }

Find out the max element in the array along with its index --> O(N)
Now find out the min element between 0 and index(got in the above step) --> O(index of Max num)

The answer is just the difference of Max and Min
Time: O(N)
Space: O(1)

@ Rajinikanth..your solution fails...consider 7,9,5,1,6,3,2