/
githubmirror
/
omim
Обзор
Документация
Войти
/
githubmirror
/
omim
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
search/algos.hpp
80 строк
2 KB
Maxim Pimenov
clang-format
15 фев 2019, 14:06
15 фев 2019, 14:06
8835036
Код
Авторство
О чём код?
#pragma once #include "base/base.hpp" #include <algorithm> #include <cstddef> #include <vector> namespace search { namespace impl { struct LS { size_t prevDecreasePos, decreaseValue; size_t prevIncreasePos, increaseValue; LS(size_t i) { prevDecreasePos = i; decreaseValue = 1; prevIncreasePos = i; increaseValue = 1; } }; } // namespace impl template <typename T, typename OutIter, typename Comp> void LongestSubsequence(std::vector<T> const & in, OutIter out, Comp cmp) { if (in.empty()) return; std::vector<impl::LS> v; v.reserve(in.size()); for (size_t i = 0; i < in.size(); ++i) v.push_back(impl::LS(i)); size_t res = 1; size_t pos = 0; for (size_t i = 0; i < v.size(); ++i) { for (size_t j = i + 1; j < v.size(); ++j) { if (cmp.Less(in[i], in[j]) && v[i].increaseValue + 1 >= v[j].increaseValue) { v[j].increaseValue = v[i].increaseValue + 1; v[j].prevIncreasePos = i; } if (cmp.Greater(in[i], in[j]) && v[i].decreaseValue + 1 >= v[j].decreaseValue) { v[j].decreaseValue = v[i].decreaseValue + 1; v[j].prevDecreasePos = i; } size_t const m = std::max(v[j].increaseValue, v[j].decreaseValue); if (m > res) { res = m; pos = j; } } } bool increasing = true; if (v[pos].increaseValue < v[pos].decreaseValue) increasing = false; while (res-- > 0) { *out++ = in[pos]; if (increasing) pos = v[pos].prevIncreasePos; else pos = v[pos].prevDecreasePos; } } } // namespace search