An algorithm for the determination of a longest increasing subsequence in a sequence

✍ Scribed by M. Orlowski; M. Pachter

• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 171 KB
• Volume: 17
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/0898-1221(89)90036-9

✦ Synopsis

We present a simple, novel and efficient algorithm for the determination of a longest increasing subsequence in a given sequence of ,, numbers. Our algorithm performs in O(,~ log r) time in the worst case, where r is the size of the output, i.e. r is the length of the longest increasing subsequence (s). The algorithm is motivated by the idea of a Young tableau that is associated with a given sequence.