Estimating the longest increasing sequence in polylogarithmic time

M. Saks, C. Seshadhri

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let $n$ denote the size of the array. Simple $O(n\log n)$ algorithms are known for…