  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)$.
