Given an unsorted Array find maximum value of A[j] - A[i] where j>i..in O(n) time

Question

This is an Amazon interview Question.I have solved this problem in O(n) using dynamic programming.But I want to know can there be more optimization than O(n)

for e.g. suppose below is the array

3 7 1 4 2 4 returns 4

5 4 3 2 1 returns Nothing

4 3 2 2 3 returns 1

This is the code i have written Code

Answer 1

Lets say you've got int A[N].

int res = -1;
int min_value = A[0];
for(int i=1; i<N; i++) {
    // A[i] - A[j] is maximal, when A[j] is minimal value from {A[0], A[1],.., A[i-1]}
    res = max(res, A[i] - min_value);
    min_value = min(min_value, A[i]);
}
return res;

Complexity O(N).

You need to examine N elements so O(N) is best what you can get.