Algorithm to find the largest drop in an array

Question

I have an algorithm question:

Given an array(assuming all the elements are intergers) of size N, find the largest drop(not necessarily continuous) : max{array[i]-array[j]} with a constraint: i>j .

The simple solution is that two loops and go through all possible values of i and j,but the time complexity is O(n*n).

And an improved solution I think is to map the indexes of the array first, sort the array and go through the array to find the largest drop. This complexity is O(nlogn).

Is there a solution with linear time complexity? And how?

PS: I once thought a linear solution: create two extra arrays, one is to record the max value of the given array from the beginning to the end, and the other to the min value from the end to the beginning.Then, go through two array one pass. However, someone thought that not correctly and taking up too big space. So I want to know a better solution. – lijuanliu

Answer 1

You need to keep track of two things:

The maximum number you have seem up to element i, and the biggest drop you have seem with respect to the biggest number (i.e. the maximum number before i, minus the element i). This will be O(n) in time and O(1) in space.

This problem is exactly the "stock buying/selling" interview question, solution can be found here: Maximum single-sell profit

Answer 2

O(n) solution without extra space:

public int maxDrop(int[] a) {
    int max = a[0];
    int maxDrop = -1;
    for (int i = 0; i < a.length; i++) {
        if (max < a[i]) {
            max = a[i];
        }
        else {
            int drop = max - a[i];
            maxDrop = Math.max(maxDrop, drop);
        }
    }
    return maxDrop;
}