Minimum Height and Sequence Constrained Longest Increasing Subsequence

Abstract

Given a string S=a1a2a3...a(subscript n), the longest increasing subsequence (LIS) problem is to find a subsequence of S such that the subsequence is increasing and its length is maximum. In this paper, we propose and solve two variants of the LIS problem. The first one is the minimum height LIS where the height means the difference between the largest and smallest elements. We propose an algorithm with O(n log n) time and O(n) space for solving it. The second one is the sequence constrained LIS (SCLIS) that given a string S and a constraint C, we are to find the LIS of S containing C as its subsequence. We propose an algorithm with O (n log(n+|C|)) time for solving it. And then we solve the SCLIS with preprocessing. We propose a preprocessing algorithm with O (n^2 log log n) time on S so that with a given sequence of positions, we can answer the SCLIS query in O(|C|+|OUTPUT |) time where the constraint is the subsequence on the given positions of S.