Home » Technical Interview Questions » Array Interview Questions » Maximum difference between two elements such as larger element comes after smaller

# Maximum difference between two elements such as larger element comes after smaller

We have given an array of n integers in which we have to find the maximum difference between two elements such as larger element comes after smaller.

## Example

Input

4  7  2  18  3  6  8  11  21

Output

19

## Approach 1 for Maximum difference between two elements

We make use of the Kadane’s approach in a modified form.

### Algorithm

1. Initialize the current_difference as the difference of the first two elements.
2. Loop through the array such that
• If the current_difference is greater than zero then add to it the difference of the consecutive array elements.(Compute Prefix Sum).
• Else current_difference is equal to the difference of the present consecutive elements.
• Compare the current_difference with the present max_difference and update it accordingly.

The approach uses Dynamic Programming and is very efficient.

### C++ Program

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {4,5,8,1,3,7,11,13,2};
int N = sizeof(arr)/sizeof(arr);

int diff = arr-arr;
int curr_sum = diff;
int max_sum = curr_sum;

for(int i=1; i<N-1; i++)
{
// Calculate current diff
diff = arr[i+1]-arr[i];

// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;

// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}

if(max_sum >= 0)
cout<<"Maximum difference is "<<max_sum<<endl;
else
cout<<"Maximum difference is not valid as array reversely sorted"<<endl;
return 0;
}```
`Maximum difference is 12`

## Approach 2 for Maximum difference between two elements

### Algorithm

1. Loop From the last of the array as we will have to check the larger number occurs later.

2. Run another loop from start and do:

a) If the present element is smaller than the number present at the index of the outer loop, then check if its difference is larger than the present difference.If yes then update the max_difference.

b) Else increment the loop counter and check for the next difference.

### C++ Program

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {4,5,8,1,3,7,11,15,2};
int N = sizeof(arr)/sizeof(arr);
int max_diff = INT_MIN;

for(int i=N-1; i>=0; i--) //start from the end so that we can check if the larger element comes later.
{
for(int j=0;j<i;j++) //select each number from start till one less than the number selected
{
if(arr[i] > arr[j]) //if the condition satisfies
{
if(arr[i] - arr[j] > max_diff) //update the max_diff
max_diff = arr[i]-arr[j];
}
}
}
cout<<"Maximum difference is "<<max_diff<<endl;
return 0;
}```
`Maximum difference is 14`

### Complexity Analysis for Maximum difference between two elements

Time Complexity: O(N2) where N is the length of the given array.  Here we check the largest element on the right side for each element that will take O(n*n) time complexity.
Space Complexity: O(1) because we just update the answer in a variable. We use constant amount of space here.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions 