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