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

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <climits> using namespace std; // Naive function to find maximum difference between two elements in // the array such that smaller element appears before the larger // element in the array int diff(int arr[], int n) { int diff = INT_MIN; for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) diff = max(diff, arr[j] - arr[i]); return diff; } // main function int main() { int arr[] = { 2, 7, 9, 5, 1, 3, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The maximum difference is " << diff(arr, n); return 0; } |

**Output: **

The maximum difference is 7

The time complexity of above solution is O(n^{2}) 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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <climits> using namespace std; // Function to calculate maximum difference between two elements in the // array such that smaller element appears before the larger element int diff(int arr[], int n) { int diff = INT_MIN; int max_so_far = arr[n-1]; // traverse the array from right and keep track the maximum element for (int i = n - 2; i >= 0; i--) { // update max if current element is greater than the maximum element if (arr[i] > max_so_far) max_so_far = arr[i]; // if the current element is less than the maximum element, // then update the difference if required else diff = max (diff, max_so_far - arr[i]); } // return difference return diff; } // main function int main() { int arr[] = { 2, 7, 9, 5, 1, 3, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The maximum difference is " << diff(arr, n); return 0; } |

**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 🙂