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[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
    Posted by
    Labels: ,