A Dynamic Algorithm for the Longest Increasing Subsequence

Abstract

We present a dynamic algorithm for the longest monotonically increasing subsequence of a finite set N ⊂ R 2 with unique x -values and with |N | = n, supporting insertions and deletions in O(n). Queries for the minimal partition into strictly decreasing subsequences are supported in O(1), queries for the maximal length L of a monotonically increasing subsequence are supported in O(1), and queries for a longest monotonically increasing subsequence are supported output-sensitively in O(L).