Fast computation of a longest increasing subsequence and application

We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, ..., n) can be computed in time O(n log log k) in the RAM model, improving the previous 30-year bound of O(n log k). The algorithm also improves on the previous O(n log log n) bound. The optimality of the new bound is an open question. Reducing the computation of a longest common subsequence (LCS) between two strings to an LIS computation leads to a simple O(n log log n)-time algorithm for two sequences having r pairs of matching symbols and an LCS of length k. Crown Copyright (C) 2010 Published by Elsevier Inc. All rights reserved.