We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under (i) inserting an element, and (ii) deleting an element of an array. In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an $\mathcal{ O}((1/\epsilon)^{ \mathcal{ O}(1/\epsilon)})$-approximation of LIS under both operations with worst-case update time $\mathcal{ \tilde O}(n^{ \epsilon})$, for any constant $\epsilon>0$. We exponentially improve on their result by designing an algorithm that maintains an $(1+\epsilon)$-approximation of LIS under both operations with worst-case update time $\mathcal{ \tilde O}(\epsilon^{ -5})$. Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification. A particularly interesting consequence of our result is an improved solution for the so-called Erd\H{ o}s-Szekeres partitioning, in which we seek a partition of a given permutation of $\{ 1,2,\ldots,n\}$ into $\mathcal{ O}(\sqrt{ n})$ monotone subsequences. This problem has been repeatedly stated as one of the natural examples in which we see a large gap between the decision-tree complexity and algorithmic complexity. The result of Mitzenmacher and Seddighin implies an $\mathcal{ O}(n^{ 1+\epsilon})$ time solution for this problem, for any $\epsilon>0$. Our algorithm (in fact, its simpler decremental version) further improves this to $\mathcal{ \tilde O}(n)$.
Categories: cs.DS