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