Live briefing
Everything about Longest increasing subsequence
Computer science problem
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. The longest increasing subsequence problem is solvable in time where denotes the length of the input sequence. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Longest increasing subsequenceA 5-minute orientation
- Skim a recent paper: Computing the longest common almost-increasing subsequenceInfluential work since 2022
- Pick up a classic book: Malliavin Calculus and Stochastic AnalysisThe most-reprinted book on the subject
- Read the landmark paper: On the distribution of the length of the longest increasing subsequence of random permutationsCited 715 times
- Go sideways: Erdős–Szekeres theoremA closely related topic
- Go sideways: Shortest common supersequenceA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
On the distribution of the length of the longest increasing subsequence of random permutations
The longest increasing subsequence in a random permutation and a unitary random matrix model
A fast algorithm for computing a longest common increasing subsequence
Fast computation of a longest increasing subsequence and application
The Length of the Longest Increasing Subsequence of a Random Mallows Permutation
Alignment of BLAST high-scoring segment pairs based on the longest increasing subsequence algorithm
Efficient algorithms for finding a longest common increasing subsequence
On the longest increasing subsequence of a circular list
🆕 Influential since 2022
Computing the longest common almost-increasing subsequence
The Preisach graph and longest increasing subsequences
The Longest Wave Subsequence Problem: Generalizations of the Longest Increasing Subsequence Problem
Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
The longest increasing subsequence problem revisited
📚 Books worth reading
Malliavin Calculus and Stochastic AnalysisFrederi Viens · 2013- 📕Surprising Mathematics of Longest Increasing SubsequencesDan Romik · 2014
The surprising mathematics of longest increasing subsequencesDan Romik · 2015
প্রোগ্রামিং কনটেস্টমোঃ মাহবুবুল হাসান · 2016
Learn Excel 2007 through Excel 2010 from Mr. ExcelBill Jelen · 2011
A TOUR OF THE WORLDMalik Mansab Khan, Muhammad Rafique Abdul Aziz · 2025
Waldara AnswersWilliam Swygard · 1975
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Erdős–Szekeres theorem In mathematics, the Erdős–Szekeres theorem asserts that, given r {\displaystyle r} and s {\displaystyle s} , any sequence of distinct real numbers with…
- Shortest common supersequence In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem…
- Algorithmically random sequence Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-fr…
- Subadditivity In mathematics, subadditivity is a property of a function that states, roughly, that evaluating the function for the sum of two elements of the domain…
- Merge-insertion sort In computer science, merge-insertion sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer…
- Longest alternating subsequence In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given…
- Bitonic sorter Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised…
- Longest common substring Wikibooks has a book on the topic of: Algorithm Implementation/Strings/Longest common substring In computer science, a longest common substring of two…