This post is completed by 1 user

  • 0
 Add to List
Medium

221. Identifying Maximum Gain from Sequential Elements

Objective: Given an array A[], write an algorithm to find the Maximum difference between two elements where the 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 the larger element appears after the smaller element.

Time complexity is O(N^2).

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 into 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 the left half and index j is in the right half of the array.
  4. Solve the above 3 subproblems recursively and the final answer will be the maximum of these 3 subproblems.
  5. This solution is very much similar to Merge sort

Time complexity is O(nlogn).

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 that 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)

Output:

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

Related Problems: