- 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(n**

^{2})## 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[1] - array[0]; /* 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[10] = {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[1] - array[0]; min = array[0]; /* 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[10] = {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 differences of adjacent elements */ 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[0]; 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[10] = {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