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

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.