Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality

In this work, we present a plethora of results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to Range-LIS is a sequence S of n real numbers and a collection Q of m query ranges and for each query in Q, the goal is to report the LIS of the sequence S restricted to that query. Our two main results are for the following generalizations of the Range-LIS problem: • 2D Range Queries: In this variant of the Range-LIS problem, each query is a pair of ranges, one of indices and the other of values, and we provide an algorithm with running time Õ(mn1/2+ n3/2 +k), where k is the cumulative length of the m output subsequences. This breaks the quadratic barrier of Õ(mn) when m=Ω(√n). Previously, the only known result breaking the quadratic barrier was of Tiskin [SODA'10] which could only handle 1D range queries (i.e., each query was a range of indices) and also just outputted the length of the LIS (instead of reporting the subsequence achieving that length). • Colored Sequences: In this variant of the Range-LIS problem, each element in S is colored and for each query in Q, the goal is to report a monochromatic LIS contained in the sequence S restricted to that query. For 2D queries, we provide an algorithm for this colored version with running time Õ(mn2/3+ n5/3 +k). Moreover, for 1D queries, we provide an improved algorithm with running time Õ(mn1/2+ n3/2 +k). Thus, we again break the quadratic barrier of Õ(mn). Additionally, we prove that assuming the well-known Combinatorial Boolean Matrix Multiplication Hypothesis, that the runtime for 1D queries is essentially tight for combinatorial algorithms.