Longest increasing subsequence

In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique. The longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics.^[1]^[2] The longest increasing subsequence problem is solvable in time $O(n\log n),$ where $n$ denotes the length of the input sequence.^[3]

^ Aldous, David; Diaconis, Persi (1999), "Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem", Bulletin of the American Mathematical Society, 36 (4): 413–432, doi:10.1090/S0273-0979-99-00796-X.
^ Romik, Dan (2015). The Surprising Mathematics of Longest Increasing Subsequences. doi:10.1017/CBO9781139872003. ISBN 9781107075832.
^ Cite error: The named reference schensted was invoked but never defined (see the help page).

[1] Aldous, David; Diaconis, Persi (1999), "Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem", Bulletin of the American Mathematical Society, 36 (4): 413–432, doi:10.1090/S0273-0979-99-00796-X.

[romik-2] Romik, Dan (2015). The Surprising Mathematics of Longest Increasing Subsequences. doi:10.1017/CBO9781139872003. ISBN 9781107075832.

[schensted-3] Cite error: The named reference schensted was invoked but never defined (see the help page).

[1]

[2]

[3]