Algorithm to find the largest drop in an array
algorithm, arrays
Solution
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
Problem
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