# Program to Find Maximum Difference Between a Pair of Elements

• Write a program to find maximum difference between elements such that larger element is after smaller element.

Given an integer array of size N, we have to maximum difference between a pair of element. Find a pair of element array[i] and array[j] such that array[j]-array[i] is maximum, array[j] > array[i] and j > i. For Example :

```Input Array : 7, 3, 9, 1, 0, -4, 7, 2, 5, 6
Maximum Difference is 11 between -4 and 7
```

Brute Force : O(n2)
• Using two for loop, generate all possible pairs of elements. Let current pair is arrayInput[i] and arrayInput[j] where j > i.
• Check if (array[j] > array[i] && arrayInput[j]-arrayInput[i]) is greater than maximum difference(maxDiff) found till now.
• If true then update maxDiff else continue.
• ## C program to find maximum difference between two elements

```#include <stdio.h>

/* This function returns the maximum difference between
two elements of array, such that larger elements
is after smaller element*/
int getMaxDiff(int *array, int size) {
/* Initialize maxDiff with diference
of first two element */
int i, j;
int maxDiff = array - array;
/* For every element, check it's difference
with all other larger elements */
for(i = 0; i < size; i++){
for(j = i+1; j < size; j++){
if((array[j] - array[i] > maxDiff) && (array[j] > array[i]))
maxDiff = array[j] - array[i];
}
}
return maxDiff;
}

int main(){
int array = {7, 3, 9, 1, 0, -4, 7, 2, 5, 6};
int maxDiff = getMaxDiff(array, 10);
printf("Maximum Difference : %d", maxDiff);
return 0;
}

```
Output
```Maximum Difference : 11
```

Optimized approach : O(n)
• Traverse inputArray from index 0 to N-1 and keep tract of the minimum element found till now(min) and maximum difference between any two element till now(maxDiff).
• Let current element is inputArray[i], difference between the current element and minimum element found till now is greater than maxDiff(array[i] - min > maxDiff) then update maxDiff.
• If array[i] is less than min, then update min.

## C program to find maximum difference two elements in linear time

```#include <stdio.h>

/* This function returns the maximum difference between
two elements of array, such that larger elements
is after smaller element */
int getMaxDiff(int *array, int size) {
int i, j, min, maxDiff;
/* Initialize maxDiff with diference
of first two element */
maxDiff = array - array;
min = array;
/* For every element, check it's difference
with min is greater than maxDiff */
for(i = 0; i < size; i++){
if(array[i] - min > maxDiff){
maxDiff = array[i] - min;
}
/* Update min */
if(array[i] < min)
min = array[i];
}
return maxDiff;
}

int main(){
int array = {7, 3, 9, 1, 0, 2, 7, 2, 5, 6};
int maxDiff = getMaxDiff(array, 10);
printf("Maximum Difference : %d", maxDiff);
return 0;
}
```
Output
```Maximum Difference : 7
```

By finding difference between adjacent elements : O(n)
• Create a temporary array and populate the difference of adjacent elements of inputArray in tempArray.(tempArray[i] = inputArray [i+1] - inputArray [i])
• Find Maximum sum sub array of tempArray. Let the maximum sum subarray is from index x to y whose sum is SUM.
• Now, Maximum difference between two elements is SUM and corresponding elements are at index x and y.
```#include <stdio.h>

int getMaxDiff(int *array, int size) {
/* Create a temporary array to store the
int i, maxDiff, diffArray[size-1];
for(i = 0; i < size-1; i++) {
diffArray[i] = array[i+1] - array[i];
}

/* Find Maximum sum sub-array if difference Array */
maxDiff = diffArray;
for(i = 1; i < size-1; i++) {
if(diffArray[i-1] > 0)
diffArray[i] += diffArray[i-1];
if (maxDiff < diffArray[i])
maxDiff = diffArray[i];
}
return maxDiff;
}

int main(){
int array = {7, 3, 9, 1, 0, 2, 7, 2, 5, 6};
int maxDiff = getMaxDiff(array, 10);
printf("Maximum Difference : %d", maxDiff);
return 0;
}
```
Output
```Maximum Difference : 7
```