Longest Increasing Subsequence

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  is .

It can be coded in the Wolfram Language as follows.

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

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.