#include<stdio.h>

int maxDiff(int a[], int n)
{
    int maxDiff = -1; // Initialize Result
 
    int maxRight = a[n-1]; // Initialize max element from right side
 
    for (int i = n-2; i >= 0; i--)
    {
        if (a[i] > maxRight)
            maxRight = a[i];
        else
        {
            int diff = maxRight - a[i];
            if (diff > maxDiff)
            {
                maxDiff = diff;
            }
        }
    }
    return maxDiff;
}   

int main()
{
  int a[] = {20, 2, 90, 10, 110};
  printf("Maximum difference is %d",  maxDiff(a, 5));
  getchar();
  return 0;
}

Output:

Maximum difference is 108

Explanation:

In above program following procedure is followed:

• The maximum element is assumed to be the last element from right side and is assigned to maxRight.
• The loop tries to find maximum element from right side, if found max element is assigned to variable maxRight.
• The difference is between max element from right and currently visited element in the array which is then compared to maxDiff if less then difference is assigned to maxDiff.
• An efficient method as time complexity is O(n) since only one loop is involved.