Какой способ найти подпоследовательности длины LIS будет наиболее эффективным по времени? ⇐ C++

[Anonymous]

Дана последовательность массива (вектора). Мне нужен метод или исправление, которое позволит найти все возрастающие подпоследовательности с длиной самой длинной возрастающей последовательности. Например: [1, 3, 2, 5, 2] должно вывести: 1 3 5 и 1 2 5

1 3 5 — первая длина LIS, равная 3. Тогда следующий — 1 2 5.

Я уже реализовал кое-что, что работает для небольших экземпляров, но как только у меня появляется массив последовательностей большего размера (размер: 1000+), программа занимает целую вечность.

Вот моя функция для длины LIS: она использует динамическое программирование и работает очень быстро

int findLISLength(const std::vector& последовательность, size_t n) { std::vector lisEnd(n + 1, 0); std::vector родитель(n, 0); длина целого = 0; for (int i = 0; i < n; ++i) { интервал низкий = 1; int high = длина; while (низкий