Maximum difference between two elements

Question

Given an array of integers, i have to find out the maximum difference between any two elements such that larger number is appearing after the smaller number in the array.I used a simple approach and took the difference with the minimum number encountered so far by keeping the track of 2 things

1.Maximum difference

2.Minimum number visited so far.

    int min_element=arr[0];
    int diff=arr[1]-arr[0];
    for(i=1;i<n;i++)
    {
        if(arr[i]-min_element>diff)
            diff=arr[i]-min_element;
        if(arr[i]<min_element)
            min_element=arr[i];
    }
    return diff;

Is there a better approach for solving this problem?

Answer 1

As it stands, your algorithm is optimal, up to a constant factor.

Reading an array of n integers takes Ω(n). Your algorithm is O(n), so you're good.