Objective: Given an array A[], write an algorithm to find Maximum difference between two elements where larger element appears after the smaller element or in other words find A[i] and A[j] such that A[j]-A[i] is maximum where j > i.
Example:
int [] A = { 2, 5, 1, 7, 3, 9, 5}; Maximum Difference between two elements A[i] and A[j] and where j > i: 8 int [] A = { 22,2, 12, 5, 4, 7, 3, 19, 5}; Maximum Difference between two elements A[i] and A[j] and where j > i: 17
Approach 1:
Naive: This problem can be easily solved using two nested loops. Take each element at a time and compare it with all the other elements and keep the track of the maximum difference elements where larger element appears after the smaller element.
Time complexity is O(N^2).
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MaxDifferenceBruteForce { | |
public static int maxDifference(int [] A){ | |
int maxDiff = –1; | |
for (int i = 0; i <A.length ; i++) { | |
for (int j = i; j <A.length ; j++) { | |
if(A[j]>A[i] && (A[j]–A[i]>maxDiff)) | |
maxDiff = A[j]–A[i]; | |
} | |
} | |
return maxDiff; | |
} | |
public static void main(String[] args) { | |
int [] A = { 2, 5, 1, 7, 3, 4, 9, 4, 5}; | |
System.out.println("Maximum Difference between two elements A[i] and A[j] and where j > i: " + maxDifference(A)); | |
} | |
} |
Approach 2:
Divide and Conquer
- We need to find the two elements A[i] and A[j] so that A[j] – A[i] is maximum and j > i
- Divide the input array into 2 parts, left Half and right half.
- We have divided the problem in 2 parts. Now we can conclude that for answer-
- Both indexes i and j are in the left half of the array.
- Both indexes i and j are in the right half of the array.
- Index i is in left half and index j is in right half of the array.
- Solve the above 3 sub problems recursively and final answer will the maximum of these 3 sub problems.
- This solution is very much similar to Merge sort
Time complexity is O(nlogn).
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MaxDifferenceDandC { | |
public int maxDifference(int [] A, int start, int end){ | |
if(start>=end){ | |
return –1; | |
} | |
int mid = start + (end–start)/2; | |
int leftDiff = maxDifference(A,start,mid); | |
int rightDiff = maxDifference(A,mid+1,end); | |
int minLeft = getMin(A, start, mid); | |
int maxRight = getMax(A, mid, end); | |
int centerDiff = maxRight – minLeft; | |
return Math.max(centerDiff, Math.max(leftDiff,rightDiff)); | |
} | |
public int getMin(int [] A, int i, int j){ | |
int min = A[i]; | |
for (int k = i+1; k <=j ; k++) { | |
if(A[k]<min) | |
min = A[k]; | |
} | |
return min; | |
} | |
public int getMax(int [] A, int i, int j){ | |
int max = A[i]; | |
for (int k = i+1; k <=j ; k++) { | |
if(A[k]>max) | |
max = A[k]; | |
} | |
return max; | |
} | |
public static void main(String[] args) { | |
MaxDifferenceDandC m = new MaxDifferenceDandC(); | |
int [] A = { 2, 5, 1, 7, 3, 4, 9, 4, 5}; | |
int start = 0; | |
int end = A.length–1; | |
System.out.println("Maximum Difference between two elements A[i] and A[j] and where j > i: " + | |
m.maxDifference(A, start, end)); | |
} | |
} |
Approach 3:
Dynamic Programming:
- Traverse the array from right to left.
- Maintain 2 variables – maxDifference (this will be our final answer), and max_so_far(maximum element we encounter while traversing the array)
- During iteration, every element has 2 choices
- Either current element is the maximum element among elements which are iterated, if yes then max_so_far = current element.
- OR current element is less than the max_so_far. If yes then update the maxDifference = max_so_far – current element.
- Once the iteration is done, return maxDifference.
Time complexity: O(n), Space complexity: O(1)
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MaxDifferenceDynamicProgramming { | |
public static int maxDifference(int [] A){ | |
int size = A.length; | |
int maxDiff = –1; | |
int max_so_far = A[size–1]; //assign the last element | |
for (int i = size – 2 ; i >0 ; i—) { | |
if(max_so_far<A[i]) | |
max_so_far = A[i]; | |
else if(max_so_far>A[i]) | |
maxDiff = Math.max(maxDiff,max_so_far–A[i]); | |
} | |
return maxDiff; | |
} | |
public static void main(String[] args) { | |
int [] A = { 12, 5, 1, 7, 3, 9, 5}; | |
System.out.println("Maximum Difference between two elements A[i] and A[j] and where j > i: " + maxDifference(A)); | |
} | |
} |
Output:
Maximum Difference between two elements A[i] and A[j] and where j > i: 8