Maximum difference in contiguous, fixed-length subsequence

Question

Define the displacement of a sequence to be the difference between the maximum and minimum elements. Given a sequence of integers, find the maximum displacement over all contiguous subsequences of length m.

For example, if our sequence is [1, 5, 7, 0, 2, -4] and m = 3,

• [1, 5, 7] has displacement 6.
• [5, 7, 0] has displacement 7.
• [7, 0, 2] has displacement 7.
• [0, 2, -4] has displacement 6.
• So the maximum displacement is 7.

If we let n denote the length of the input sequence, then my solution below runs in O(nlog(m)) time. Is there any way to do better? I feel like there must be a linear-time algorithm I'm missing. For the purposes of this question, all I care about is the asymptotic time complexity.

#include <vector>
#include <set>
#include <iostream>
int find_max_displacement(std::vector<int> seq, int m){
    std::multiset<int> subseq;
    // insert the m items of first subsequence into tree
    for (int i = 0; i < m; i++){
        subseq.insert( seq[i] );
    }
    int max_disp = *subseq.rbegin() - *subseq.begin(); // max minus min
    for (int i = 0; i < seq.size() - m; i++){
        subseq.erase(subseq.find(seq[i]));  // kick oldest element out of subsequence
        subseq.insert( seq[i+m] );          // insert new element into subsequence
        int new_disp = *subseq.rbegin() - *subseq.begin();
        if (new_disp > max_disp){
            max_disp = new_disp;
        }
    }
    return max_disp;
}
int main(){
    std::vector<int> arr {1, 5, 7, 0, 2, -4};
    int max_disp = find_max_displacement(arr, 3);
    std::cout << max_disp << std::endl;
    return 0;
}

Answer 1

You are right, there is a linear time algorithm for this. You can compute an array with the sliding maximum and an array with the sliding minimum and find the largest difference between these two arrays.

Computing a sliding maximum in linear time is a standard problem, there is a good explanation of different techniques here. In case the link breaks, here is the description of the linear time algorithm from that link:

The algorithm presented here is the ascending minima algorithm; it requires O(n) time and O(k) space. The general idea is to locate the minimum in the window, then the minimum in the remainder of the window, and so. Values between the ascending minima can be ignored.

More formally, let W be a vector of values of length k. Define the sequence of ascending mimima, A, as follows:

Let A[0] be the minimum value in W and for j>0 let A[j] be the minimum value in W with index greater than the index of A[j-1]. (If two locations have the same minimum value take the later one.) Example:

 W = 5,2,8,6,4,7 
 A = 2,4,7 

Evidently the length of A is 1 if the minimum in W is the last element in W and k if W is monotonic increasing. Now suppose that we have a window W on V and that we know the ascending minima vector A. Consider what happens when we move the window one location. We add one element at the end of the window and remove one element from the beginning of the window. Let x be the newly added element. Then A can be updated by

a: removing all elements of A greater than or equal to x,

b: appending x to A,

c: and removing the initial element of A if it is being removed from the window.

We do not need to record the window; all we need is the ascending minima sequence. However it is necessary to record when an entry in the sequence will be deleted from the window. For this reason it is useful if the elements of A have two fields, the first being a value from V, i.e., V[i] for some i, and the second being the index when the entry will disappear from the window. This happens k entries later.

Since the length of A is bounded and since A is a queue, it is natural to store it in a ring buffer.

Steps (b) and (c) are straightforward without significant alternatives. In step (a) we need to locate the last value in A that is less than the newly added x. At first sight it might seem that a binary search of A would be optimal. This is not the case; the optimal search is from back to front in a simple loop.

The proof is simple enough; the linear search loop deletes elements one by one with an O(1) time cost for each deletion. On average the number of deletions from A is the same as the number of additions. The upshot is that the average time cost of moving the window one location is O(1).