A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem

• In this paper we present a divide and conquer approach to solve the longest increasing subsequence problem.
• Our divide and conquer algorithm runs in O(n log n) time and hence is optimal in the comparison model.
• In the sequel, using our divide and conquer approach we present a work optimal parallel algorithm for the problem.

In this paper, we present a divide and conquer approach to solve the problem of computing a longest increasing subsequence. Our approach runs in O(nlogn) time and hence is optimal in the comparison model. In the sequel, we show how we can achieve a work-optimal parallel algorithm using our divide and conquer approach.