On Generating and Counting All the Longest Increasing Subsequences
スポンサーリンク
概要
- 論文の詳細を見る
Suppose that we are given a sequence of n distinct positive integers 1, 2, ..., n. We consider problems generating and counting all the longest increasing subsequences in a given sequence An=a_1a_2 ... a_n. A generating algorithm is established by using a backtrack technique and requires the running time of max {O(n^2),O(l(A_n)m(A_n))}, where l(A_n) is the total number of the longest increasing subsequences in A_n and m(A_n) is the length of the longest increasing subsequence in A_n. A counting algorithm is established by using a dynamic programming technique and requires the running time of O(n^2).
- 一般社団法人情報処理学会の論文
- 1984-03-31
著者
関連論文
- Immunohistochemical Analysis of Cell Proliferation and Suppression of Ameloblastoma with Special Reference to Plexiform and Follicular Ameloblastoma
- Genetic Controls of Susceptibility and Resistance to 4-Nitroquinoline 1-Oxide-induced Tongue Carcinomas in Rats
- Specificities of the Early Body Formation in the Lancelet Embryo
- Expressions of junB and c-fos are enhanced in 4-nitroquinoline 1-oxide-induced rat tongue cancers
- Generation of Permutations by Using an Input Restricted-deque or an Output Restricted-deque
- Generation of Stack Sequences in Lexicographical Order
- 10. BMP4 induce ectopic cartilage formation in the mouse embryonal mandibular process : BMP4 mediates Msx2 and Sox9 expression during chondrogenesis.
- Generation of Permutations by Using a Stack or a Queue
- An Efficient Algorithm for Generating all Partitions of the Set{1, 2, ..., n}
- A Note on Enumerating Combinations in Lexicographical Order
- Systematic Method for Determining the Number of Multiplications Required to Compute x^m, Where m is a Positive Integer
- On Generating and Counting All the Longest Increasing Subsequences
- An O(1) Time Algorithm for Generating Fibonacci Strings(Special Issue on Selected Papers from LA Symposium)
- Generation of Binary Trees from Stack Permutations