Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given an array A[], write an algo­rithm to find Max­i­mum dif­fer­ence between two ele­ments where larger ele­ment appears after the smaller ele­ment or in other words find A[i] and A[j] such that A[j]-A[i] is max­i­mum where j > i.

Exam­ple:

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 prob­lem can be eas­ily solved using two nested loops. Take each ele­ment at a time and com­pare it with all the other ele­ments and keep the track of the max­i­mum dif­fer­ence ele­ments where larger ele­ment appears after the smaller element.

Time com­plex­ity is O(N^2).

Code:

Approach 2:

Divide and Conquer

  1. We need to find the two ele­ments A[i] and A[j] so that A[j] – A[i] is max­i­mum and j > i
  2. Divide the input array into 2 parts, left Half and right half.
  3. We have divided the prob­lem in 2 parts. Now we can con­clude 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 prob­lems recur­sively and final answer will the max­i­mum of these 3 sub problems.
  5. This solu­tion is very much sim­i­lar to Merge sort

Time com­plex­ity is O(nlogn).

Code:

Approach 3:

Dynamic Pro­gram­ming:

  1. Tra­verse the array from right to left.
  2. Main­tain 2 vari­ables — maxD­if­fer­ence (this will be our final answer), and max_so_far(maximum ele­ment we encounter while tra­vers­ing the array)
  3. Dur­ing iter­a­tion, every ele­ment has 2 choices
    1. Either cur­rent ele­ment is the max­i­mum ele­ment among ele­ments which are iter­ated, if yes then max_so_far = cur­rent element.
    2. OR cur­rent ele­ment is less than the max_so_far. If yes then update the maxD­if­fer­ence = max_so_far – cur­rent element.
  4. Once the iter­a­tion is done, return maxDifference.

Time com­plex­ity: O(n), Space com­plex­ity: O(1)

Code:

Out­put:

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

You may also like...

  • zsal­abc

    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 prob­lem is the i >0 in the for loop, it should be i >= 0

    • tuto­ri­al­hori­zon

      yes. Thanks for point­ing it out. Will cor­rect it