# 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: 8int[] 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**

- 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:**

**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:**

**Output:**

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

I think the Approach 2 – Dynamic Programming 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

yes. Thanks for pointing it out. Will correct it