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 {6,3,4,8,10,5,7,1,9,2} is {3,4,5,7,9}, whereas the longest contiguous subsequence is {3,4,8,10}.

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

See also

Longest Increasing Subsequence, Permutation

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Longest Increasing Scattered Subsequence

Cite this as:

Weisstein, Eric W. "Longest Increasing Scattered Subsequence." From MathWorld--A Wolfram Web Resource.

Subject classifications