# Maximum Difference Between Two Elements Such that Larger Element Appears After the Smaller Number

Posted in

Vinay Khatri
Last updated on July 21, 2024

## Problem

Find the maximum difference between two array elements such that the bigger element appears after, the smaller.

## Brute Force approach

Utilize two loops. Pick items one by one in the outer loop and in the inner loop, compute the difference between the selected element and every other element in the array and compare the difference to the largest difference determined so far.  This takes ``` O(N ``` ``` 2 ``` ``` ) ``` time. Can we do better? Let’s see!

## Efficient approach

In this technique, instead of taking the difference between the selected element and every other element, we take the difference between the selected element and the smallest element found thus far. So we must keep two things on track:

1. The greatest difference discovered thus far.
2. The smallest number of elements viewed so far.

This approach takes only O(N) time and O(1) space.

### C Programming

```#include<stdio.h>
int solve(int arr[], int n)
{
int ans = arr[1] - arr[0];   //keep track of answer
int minElement = arr[0];  //keep track of minimum element
int i;
for(i = 1; i < n; i++)
{
if (arr[i] - minElement > ans)        //update answer
ans = arr[i] - minElement;
if (arr[i] < minElement)
minElement = arr[i];
}
return ans;
}

void main(){
int a[]={1, 2, 3, 4, 7, 3, 5};
int n = sizeof(a)/sizeof(a[0]);
printf("%d",solve(a, n));
}```

Output

`6`

### C++ Programming

```#include <bits/stdc++.h>
using namespace std;

int solve(int arr[], int n)
{
// max difference
int ans = arr[1] - arr[0];

// minimum element
int minElement = arr[0];
for(int i = 1; i < n; i++)
{
if (arr[i] - minElement > ans)
ans = arr[i] - minElement;

if (arr[i] < minElement)
minElement = arr[i];
}

return ans;
}

int main(){
int a[]={1, 2, 3, 4, 7, 3, 5};
int n = sizeof(a)/sizeof(a[0]);
cout<<solve(a, n);
}```

Output

`6`

### Python Programming

```def solve(arr, n):
ans = arr[1] - arr[0]  #keep track of difference
minElement = arr[0]    #keep track of minimum element

for i in range( 1, n ):
if (arr[i] - minElement > ans):  #update answer
ans = arr[i] - minElement

if (arr[i] < minElement):
minElement = arr[i]
return ans

l = [1, 2, 3, 4, 7, 3, 5]

n = len(l)

print(solve(l,n))```

Output 6 People are also reading: