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++ implementation –
 

Download   Run Code

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++ implementation –
 

Download   Run Code

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

 
Application: Calculating maximum profit by buying and selling a share at-most once.

 
Exercise: Extend the second solution to print pair having maximum difference.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂