finding the maximum increase in an random array

Question

Suppose that I have an array of random reals, how do I the indices pair (i, j) where j<i and

maximise (a[j] - a[i]) in O(n ln(n)) time

n ln n sugguest recursions. So I was thinking of sorting the array in n ln n sort. but then the min and mix of the sorted array might not satisfy j<i

The difference a[j]-a[i] depends on all i , j so scanning all the possible permutation is O(n^2). Does anybody have a suggestion on how I can divide the problem space?

Answer 1

If I understand you correctly, you want to find max(a[j] - a[i]) among all pairs (i, j) where j < i.

You can do it in O(n) without much problem.

For each index i, to maximize a[j] - a[i] expression we need to find max(a[j]) on interval [0 .. i - 1]. So, let's move from left to right (increase i) and keep current maximum value of a[j].

int maxa = a[0];
for (int i = 1; i < n; ++i) {
    int current = maxa - a[i];
    if (current > best) {
        best = current;
    }
    maxa = max(maxa, a[i]);
}

Answer 2

Sort the array, but keep track of the original position of each element. Then scan through the array starting from both ends and working your way toward the middle until you find a pair that was originally in the correct order.