Longest Increasing Scattered Subsequence

The longest increasing scattered subsequence is the longest subsequence of increasing terms, where intervening nonincreasing terms may be dropped. Finding the largest scattered subsequence is a much harder problem. The longest increasing scattered subsequence of a partition can be found using LongestIncreasingSubsequence[p] in the Wolfram Language package Combinatorica` . For example, the longest increasing scattered subsequence of the permutation  is , whereas the longest contiguous subsequence is .

Any sequence of  distinct integers must contain either an increasing or decreasing scattered subsequence of length  (Erdős and Szekeres 1935; Skiena 1990, p. 75).

REFERENCES:

Erdős, P. and Szekeres, G. "A Combinatorial Problem in Geometry." Compos. Math. 2, 464-470, 1935.

Schensted, C. "Longest Increasing and Decreasing Subsequences." Canad. J. Math. 13, 179-191, 1961.

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.