Given an integer array, find the maximum difference between two elements in it such that the 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)

Practice this problem

A naive solution is to consider every pair present in the array and keep track of the maximum difference found so far. Following is the C, Java, and Python program that demonstrates it:

C


Download  Run Code

Output:

The maximum difference is 7

Java


Download  Run Code

Output:

The maximum difference is 7

Python


Download  Run Code

Output:

The maximum difference is 7

The time complexity of the above solution is O(n2) and doesn’t require any extra space, where n is the size of the input.

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

The algorithm can be implemented as follows in C, Java, and Python:

C


Download  Run Code

Output:

The maximum difference is 7

Java


Download  Run Code

Output:

The maximum difference is 7

Python


Download  Run Code

Output:

The maximum difference is 7

The time complexity of the above solution is O(n) and doesn’t require any extra space. The primary application of this problem is calculating the maximum profit by buying and selling a share at most once.

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