TOPICS
Search

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

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.

Referenced on Wolfram|Alpha

Longest Increasing Scattered Subsequence

Cite this as:

Weisstein, Eric W. "Longest Increasing Scattered Subsequence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LongestIncreasingScatteredSubsequence.html

Subject classifications