On computing the length of longest increasing subsequences

摘要: Let S = x"1, x"2, ... x"n be a sequence of n distinct elements from linearly ordered set. We consider the problem determining length longest increasing subsequences S. An algorithm which performs this task is described and shown to perform log n-n + O(n) comparisons in its worst case. This case behavior best possible.