To find the maximum difference of arr[j] - arr[i] such that j>i (efficient way)

Question - 

Given an array, your task  is to find the maximum difference of arr[j] - arr[i] such that j>i.

Example - 

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

Output : maximum difference is : 8 

hint - maximum difference is of 10-2 = 8

Approach - 

We know that max difference is max value - min value such that index of max value is greater than index of min value. so we create a minimum value and always find the maximum difference with maximum difference-min value and update the min value.

Implementation -

#include<iostream>

using namespace std;

void findmaxdifference(int arr[],int n)

{

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

    int minval=arr[0];

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

        maxdiff=max(maxdiff,arr[i]-minval);

        minval=min(minval,arr[i]);

    }

    cout<<"Maximum difference is  : "<<maxdiff<<endl;

}

int main()

{

    int n;

    cout<<"Enter value of n : ";cin>>n;

    int arr[n];

    cout<<"Enter elements : "<<endl;

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

        cin>>arr[i];

    findmaxdifference(arr,n);

    return 0;

}

Code on compiler

Time complixity - O(n)

Extra space - O(1)