Максимальная разница в непрерывной подпоследовательности фиксированной длины
Определите смещение последовательности как разницу между максимальным и минимальным элементами.
Для заданной последовательности целых чисел найдите максимальное смещение по всем смежным подпоследовательностям длины. m,
Например, если наша последовательность [1, 5, 7, 0, 2, -4] и m = 3,
- [1, 5, 7] имеет смещение 6.
- [5, 7, 0] имеет смещение 7.
- [7, 0, 2] имеет смещение 7.
- [0, 2, -4] имеет смещение 6.
- Таким образом, максимальное смещение составляет 7.
Если мы будем обозначать n как длину входной последовательности, то мое решение, приведенное ниже, выполняется за время O (nlog (m)). Есть ли способ сделать лучше? Я чувствую, что должен быть алгоритм линейного времени, который мне не хватает.
Для целей этого вопроса все, что меня волнует, это асимптотическая сложность времени.
#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;
}
Решение
Вы правы, для этого есть линейный алгоритм времени. Вы можете вычислить массив с скользящим максимумом и массив с скользящим минимумом и найти наибольшую разницу между этими двумя массивами.
Вычисление скользящего максимума в линейном времени является стандартной проблемой, есть хорошее объяснение различных методов Вот. В случае разрыва связи вот описание алгоритма линейного времени из этой ссылки:
Алгоритм, представленный здесь, является алгоритмом восходящих минимумов; Это
требует 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Очевидно, длина А равна 1, если
минимум в W является последним элементом в W и k, если W является монотонным
растет. Теперь предположим, что у нас есть окно W на V и что мы знаем
восходящий минимум векторов А. Рассмотрим, что происходит, когда мы перемещаем
окно одно место. Мы добавляем один элемент в конце окна и
удалить один элемент из начала окна. Пусть х будет
Недавно добавленный элемент. Тогда А можно обновитьa: удаление всех элементов из A, больших или равных x,
б: добавление х к А,
c: и удаление начального элемента A, если он удаляется из окна.
Нам не нужно записывать окно; все что нам нужно это
последовательность возрастающих минимумов. Однако необходимо записать, когда
запись в последовательности будет удалена из окна. По этой причине
это полезно, если элементы A имеют два поля, первое из которых является
значение из V, то есть V [i] для некоторого i, а второе является индексом
когда запись исчезнет из окна. Бывает k записей
потом.Поскольку длина A ограничена и A является очередью, это естественно
хранить его в кольцевом буфере.Шаги (b) и (c) просты без значительного
альтернативы. На шаге (а) нам нужно найти последнее значение в A, которое
меньше вновь добавленного х. На первый взгляд может показаться, что
бинарный поиск A будет оптимальным. Это не вариант; оптимальный
поиск осуществляется в простом цикле.Доказательство достаточно простое; Цикл линейного поиска удаляет элементы
один за другим с затратами времени O (1) для каждого удаления. В среднем
количество удалений из A равно количеству добавлений.
В итоге средняя стоимость перемещения окна на одно место
является O (1).
Другие решения