Maximum difference between two elements such that larger element appears after the smaller number

Maximum difference between two elements such that larger element appears after the smaller number

Given an array arr[] of integers, find out the maximum difference between any two elements such that larger element appears after the smaller number.

Method 1 (Simple)

#include<stdio.h>

/* The function assumes that there are at least two

   elements in array.

   The function returns a negative value if the array is

   sorted in decreasing order.

   Returns 0 if elements are equal */

int maxDiff(int arr[], int arr_size)

{    

  int max_diff = arr[1] - arr[0];

  int i, j;

  for (i = 0; i < arr_size; i++)

  {

    for (j = i+1; j < arr_size; j++)

    {       

      if (arr[j] - arr[i] > max_diff)  

         max_diff = arr[j] - arr[i];

    }   

  }         

  return max_diff;

}   

/* Driver program to test above function */

int main()

{

  int arr[] = {1, 2, 90, 10, 110};

  printf("Maximum difference is %d",  maxDiff(arr, 5));

  getchar();

  return 0;

}

Output :

Maximum difference is 109

Method 2 (Tricky and Efficient)

#include<stdio.h>

/* The function assumes that there are at least two

   elements in array.

   The function returns a negative value if the array is

   sorted in decreasing order.

   Returns 0 if elements are equal  */

int maxDiff(int arr[], int arr_size)

{

  int max_diff = arr[1] - arr[0];

  int min_element = arr[0];

  int i;

  for(i = 1; i < arr_size; i++)

  {      

    if (arr[i] - min_element > max_diff)                              

      max_diff = arr[i] - min_element;

    if (arr[i] < min_element)

         min_element = arr[i];                    

  }

  return max_diff;

}   

/* Driver program to test above function */

int main()

{

  int arr[] = {1, 2, 6, 80, 100};

  int size = sizeof(arr)/sizeof(arr[0]);

  printf("Maximum difference is %d",  maxDiff(arr, size));

  getchar();

  return 0;

}

Output:

Maximum difference is 109

Method 3 (Another Tricky Solution)

#include<stdio.h>

int maxDiff(int arr[], int n)

{

    // Create a diff array of size n-1. The array will hold

    //  the difference of adjacent elements

    int diff[n-1];

    for (int i=0; i < n-1; i++)

        diff[i] = arr[i+1] - arr[i];

    // Now find the maximum sum subarray in diff array

    int max_diff = diff[0];

    for (int i=1; i<n-1; i++)

    {

        if (diff[i-1] > 0)

            diff[i] += diff[i-1];

        if (max_diff < diff[i])

            max_diff = diff[i];

    }

    return max_diff;

}

/* Driver program to test above function */

int main()

{

    int arr[] = {80, 2, 6, 3, 100};

    int size = sizeof(arr)/sizeof(arr[0]);

    printf("Maximum difference is %d",  maxDiff(arr, size));

    return 0;

}

Output:

Maximum difference is 98

Examples :

Input : arr = {2, 3, 10, 6, 4, 8, 1}

Output : 8

Input : arr = {7, 9, 5, 6, 3, 2}

Output : 2