Число всех возрастающих подпоследовательностей в данной последовательности?

Возможно, вы слышали об хорошо известной проблеме поиска самой длинной возрастающей подпоследовательности . Оптимальный алгоритм имеет сложность O (n * log (n)) .

Я думал о проблеме поиска всех возрастающих подпоследовательностей в заданной последовательности. Я нашел решение проблемы, в которой нам нужно найти ряд возрастающих подпоследовательностей длины k , которые имеют O (n * k * log (n)) сложность (где n - длина последовательности).

Конечно, этот алгоритм можно использовать для моей задачи, но тогда решение имеет O (n * k * log (n) * n) = O (n ^ 2 * k * log (n)) сложность, я полагаю. Я думаю, что должно быть лучшее (я имею в виду - более быстрое) решение, но я его еще не знаю.

Если вы знаете, как решить задачу поиска всех возрастающих подпоследовательностей в заданной последовательности в оптимальном время / сложность (в данном случае оптимальное = лучше, чем O (n ^ 2 * k * log (n))) , дайте мне знать об этом.

В конце: эта проблема - не домашнее задание. В моей лекции упоминалась проблема самой длинной возрастающей подпоследовательности, и я начал думать об общей идее всех возрастающих подпоследовательностей в данной последовательности.