# Find maximum difference between two elements in the array by satisfying given constraints

Given an array of integers, find the maximum difference between two elements in the array such that smaller element appears before the larger element.

For example,

Input:  { 2, 7, 9, 5, 1, 3, 5 }

Output: The maximum difference is 7

The pair is (2, 9)

Naive solution is to consider every pair present in the array and keep track of maximum difference found so far.

## C

Output:

The maximum difference is 7

## Java

Output:

The maximum difference is 7

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).

We can solve this problem in linear time. The idea is to traverse the array from the right and keep track of maximum difference found so far. If the current element is less than the maximum element found so far and their difference is more than maximum difference found so far, then we update the maximum difference with current difference.

## C

Output:

The maximum difference is 7

## Java

Output:

The maximum difference is 7

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

One major application of this problem is to calculate maximum profit by buying and selling a share at-most once.

Exercise: Extend the second solution to print pair having maximum difference.     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂  