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 ![<span style=]()
{6,3,4,8,10,5,7,1,9,2}" src="https://mathworld.wolfram.com/images/equations/LongestIncreasingScatteredSubsequence/Inline1.gif" style="height:15px; width:159px" /> is ![<span style=]()
{3,4,5,7,9}" src="https://mathworld.wolfram.com/images/equations/LongestIncreasingScatteredSubsequence/Inline2.gif" style="height:15px; width:77px" />, whereas the longest contiguous subsequence is ![<span style=]()
{3,4,8,10}" src="https://mathworld.wolfram.com/images/equations/LongestIncreasingScatteredSubsequence/Inline3.gif" style="height:15px; width:69px" />.
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.
