主题
Search

最长递增散乱子序列

最长递增散乱子序列是在递增项的最长子序列，其中可以删除中间的非递增项。 找到最大散乱子序列是一个更难的问题。 分割的最长递增散乱子序列可以使用LongestIncreasingSubsequence[p] 在 Wolfram 语言 包中Combinatorica`例如，排列 {6,3,4,8,10,5,7,1,9,2} 的最长递增散乱子序列是 {3,4,5,7,9}，而最长连续子序列是 {3,4,8,10}。

任何 n^2+1 个不同整数的序列必须包含长度为 n+1 的递增或递减散乱子序列 (Erdős 和 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.

在 上被引用

最长递增散乱子序列

请引用为

Weisstein, Eric W. “最长递增散乱子序列。” 来自 Web 资源。 https://mathworld.net.cn/LongestIncreasingScatteredSubsequence.html

主题分类