TOPICS
Search

Longest Increasing Subsequence

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The longest increasing (contiguous) subsequence of a given sequence is the subsequence of increasing terms containing the largest number of elements. For example, the longest increasing subsequence of the permutation {6,3,4,8,10,5,7,1,9,2} is {3,4,8,10}.

It can be coded in the Wolfram Language as follows. 

  <<Combintorica`
  LongestContinguousIncreasingSubsequence[p_] :=
    Last[
    Split[Sort[Runs[p]], Length[#1] >= Length[#2]&]
    ]

See also

Longest Increasing Scattered Subsequence

Explore with Wolfram|Alpha

References

Pemmaraju, S. and Skiena, S. "Longest Increasing Subsequences." §4.4.6 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 170-172, 2003.Skiena, S. "Longest Increasing Subsequences." §2.3.6 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 73-75, 1990.

Referenced on Wolfram|Alpha

Longest Increasing Subsequence

Cite this as:

Weisstein, Eric W. "Longest Increasing Subsequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LongestIncreasingSubsequence.html

Subject classifications