Maximum difference in continuous fixed-length subsequences

Question

Define the sequence offset as the difference between the maximum and minimum elements. Given a sequence of integers, find the maximum offset over all adjacent subsequences of length m.

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

• [1, 5, 7] has an offset of 6.
• [5, 7, 0] has an offset of 7.
• [7, 0, 2] has an offset of 7.
• [0, 2, -4] has an offset of 6.
• Thus, the maximum offset is 7.

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

#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 calculate an array with a maximum moving maximum and an array with a moving minimum and find the largest difference between the two arrays.

, . :

; O (n) O (k). , , .. .

W - k. , A, :

A [0] - W j > 0 A [j] - W , , A [j-1]. ( , .) :

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

, A 1, W W k, W . , W V . , , . . x - . A

a: A, x,

b: x A,

c: A, .

; , , . , . , A , V, V [i] i, - . k .

A A , .

(b) (c) . () , , x. , A . ; .

; O (1) . A . , O (1).