Finding a O(n) solution to: max difference of pairs array question

Problem Detail: 

I don't know an O(n) solution to the following:

Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in the array than the other.

Ex: alg({9, 2, 6, 7}) = 5

It seems straightforward, yet it eludes me.

Asked By : Robert Gawdzik

Answered By : Mantas Matelis

Create an array considering the minimum value seen so far in the array (in O(n)).

Ex. (9, 2, 2, 2)

Create an array containing the differences between the previous array and the original array (again, in O(n)).

Ex. (0, 0, 4, 5)

Find the maximum value in the array (O(n)). In this case, the answer is 5 as required.

This can be done in O(1) memory and only one pass if a few optimizations are made.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20056