Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Hide Buttons

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

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:

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:

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:

Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • zsalabc

    I think the Approach 2 – Dynamic Pro­gram­ming code does not work well with input:

    int [] A = { 1, 12, 5, 1, 7, 3, 9, 5};

    The problem is the i >0 in the for loop, it should be i >= 0

    • tutorialhorizon

      yes. Thanks for pointing it out. Will correct it

%d bloggers like this: