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
|
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 |
#include <stdio.h> #include <limits.h> // Utility function to find maximum of two numbers int max(int x, int y) { return (x > y) ? x : y; } // 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]); printf("The maximum difference is %d", diff(arr, n)); return 0; } |
Output:
The maximum difference is 7
Java
|
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 |
class Util { // Naive function to find maximum difference between two elements in // the array such that smaller element appears before the larger // element in the array public static int diff(int[] A) { int diff = Integer.MIN_VALUE; for (int i = 0; i < A.length - 1; i++) { for (int j = i + 1; j < A.length; j++) { diff = Integer.max(diff, A[j] - A[i]); } } return diff; } // main function public static void main(String[] args) { int[] A = { 2, 7, 9, 5, 1, 3, 5 }; System.out.print("The maximum difference is " + diff(A)); } } |
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
|
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 40 41 42 |
#include <stdio.h> #include <limits.h> // Utility function to find maximum of two numbers int max(int x, int y) { return (x > y) ? x : y; } // 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]); printf("The maximum difference is %d", diff(arr, n)); return 0; } |
Output:
The maximum difference is 7
Java
|
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 |
class Util { // Function to calculate maximum difference between two elements in the // array such that smaller element appears before the larger element public static int diff(int[] A) { int diff = Integer.MIN_VALUE; int n = A.length; int max_so_far = A[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 max element if (A[i] > max_so_far) { max_so_far = A[i]; } // if the current element is less than the maximum element, // then update the difference if required else { diff = Integer.max(diff, max_so_far - A[i]); } } // return difference return diff; } // main function public static void main(String[] args) { int[] A = { 2, 7, 9, 5, 1, 3, 5 }; System.out.print("The maximum difference is " + diff(A)); } } |
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.
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Please correct the solution..it does not satisfy for all cases…descending array is one of the case
Thanks for sharing your concerns. A descending array is not a valid input since it violates the problem constraints that smaller element appears before the larger element in the array.
There is no maximum difference for that test case according to the constraint.