Improved dynamic algorithms for longest increasing subsequence
Tomasz Kociumaka, Saeed Seddighin · 2021
We study dynamic algorithms for the longest increasing subsequence (LIS) problem. A dynamic LIS algorithm maintains a sequence subject to operations of the following form arriving one by one: insert an element, delete an element, or substitute an element for another. After each update, the algorithm must report the length of the longest increasing subsequence of the current sequence.