Maximum difference between two elements where larger element appears after the smaller element

by

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:


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));
}
}

view raw

MaxDifferenceBruteForce.java

hosted with ❤ by GitHub


Approach 2:

Divide and Conquer

  1. We need to find the two elements A[i] and A[j] so that A[j] – A[i] is maximum and j > i
  2. Divide the input array into 2 parts, left Half and right half.
  3. We have divided the problem in 2 parts. Now we can conclude that for answer-
    1. Both indexes i and j are in the left half of the array.
    2. Both indexes i and j are in the right half of the array.
    3. Index i is in left half and index j is in right half of the array.
  4. Solve the above 3 sub problems recursively and final answer will the maximum of these 3 sub problems.
  5. This solution is very much similar to Merge sort

Time complexity is O(nlogn).

Code:


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));
}
}

view raw

MaxDifferenceDandC.java

hosted with ❤ by GitHub


Approach 3:

Dynamic Programming:

  1. Traverse the array from right to left.
  2. Maintain 2 variables – maxDifference (this will be our final answer), and max_so_far(maximum element we encounter while traversing the array)
  3. During iteration, every element has 2 choices
    1. Either current element is the maximum element among elements which are iterated, if yes then max_so_far = current element.
    2. OR current element is less than the max_so_far. If yes then update the maxDifference = max_so_far – current element.
  4. Once the iteration is done, return maxDifference.

Time complexity: O(n), Space complexity: O(1)

Code:


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));
}
}

view raw

MaxDifferenceDynamicProgramming.java

hosted with ❤ by GitHub


Output:

Maximum Difference between two elements A[i] and A[j] and where j > i: 8

Related Posts: