  In this paper, we provide new approximation algorithms for dynamic variations
of the longest increasing subsequence (\textsf{LIS}) problem, and the
complementary distance to monotonicity (\textsf{DTM}) problem. In this setting,
operations of the following form arrive sequentially: (i) add an element, (ii)
remove an element, or (iii) substitute an element for another. At every point
in time, the algorithm has an approximation to the longest increasing
subsequence (or distance to monotonicity). We present a
$(1+\epsilon)$-approximation algorithm for \textsf{DTM} with polylogarithmic
worst-case update time and a constant factor approximation algorithm for
\textsf{LIS} with worst-case update time $\tilde O(n^\epsilon)$ for any
constant $\epsilon > 0$.% $n$ in the runtime denotes the size of the array at
the time the operation arrives.
  Our dynamic algorithm for \textsf{LIS} leads to an almost optimal algorithm
for the Erd\"{o}s-Szekeres partitioning problem. Erd\"{o}s-Szekeres
partitioning problem was introduced by Erd\"{o}s and Szekeres in 1935 and was
known to be solvable in time $O(n^{1.5}\log n)$. Subsequent work improve the
runtime to $O(n^{1.5})$ only in 1998. Our dynamic \textsf{LIS} algorithm leads
to a solution for Erd\"{o}s-Szekeres partitioning problem with runtime $\tilde
O_{\epsilon}(n^{1+\epsilon})$ for any constant $\epsilon > 0$.
