algorithm – Largest increasing subsequence faster than O (n log (n))

Question:

There is a classical problem of finding the largest increasing subsequence of a given sequence. I know of several solutions to it, in O (n ^ 2) and O (n log (n)). Are there faster algorithms for solving this problem? Is there a theoretical lower limit greater than Omega (n)?

UPD: it is the subsequence that is searched for, not the substring. I use this definition of a subsequence, it seemed to me that it is generally accepted. Among the sequence [1, 2, 3, 4, 5] [1, 4, 5] is a subsequence, but not [5, 3].

Answer:

The wikipedia article states that there is a lower bound for comparison-based algorithms, since it says that n log2 n – n log2log2 n + O (n) comparisons are optimal up to a constant in O (n)

Scroll to Top