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.