Algorithm to find the largest drop in an array

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

---

Create new 2 arrays:

max[i] = max { arr[0], arr[1], ..., arr[i] }
min[i] = min { arr[n-1], arr[n-2], ..., arr[i] }
(max is the maximum from first to i, min is the minimum from i to last)

Now, iterate the auxilary arrays and find the maximum difference max[i] - min[i]

This requires 3 iterations overall and is thus O(n) .

Proof of correctness (guidelines):

Let the biggest drop be from index i to index j , where i<j :

Then, max[i] >= arr[j] (because we already passed it), and also min[i] <= arr[i] - thus max[j] - min[j] >= arr[i] - arr[j] , and the answer provided by the algorithm is at least as good as the optimal.

Also, since the biggest drop is i,j , there cannot be any k<j such that arr[k] < arr[i] , because then the biggest drop will be from arr[k] to arr[j] . Similary - there cannot be k>j such that arr[k] < arr[j] , for the same reasons - and thus max[j]-min[j] <= arr[i] - arr[j]

From the above we can conclude that max[j]-min[j] = arr[i] - arr[j] . All is left for a formal complete proof is show that for each k you get max[k]-min[k] <= max[j] - min[j] , and this is indeed the case, otherwise there are some u<k , v>k such that max[k]=arr[u], min[k]=arr[v] , and you get that arr[u] - arr[v] > arr[i] - arr[j] , which contradicts the fact that i,j is the biggest drop.

QED

---

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 (ie 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

---

O（n）解决方案无额外空间：

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;
}

链接地址: http://www.djcxy.com/p/94612.html

上一篇: FileReader读取未定义的文件结果

下一篇: 算法来查找数组中最大的下拉列表