Title: EDC-LISP: an efficient divide-and-conquer solution to the longest increasing subsequence problem

Authors: Seema Rani; Dharmveer Singh Rajpoot

Addresses: Computer Science and Engineering Department, Jaypee Institute of Information Technology, Noida – 201309, India ' Computer Science and Engineering Department, Jaypee Institute of Information Technology, Noida – 201309, India

Abstract: The longest increasing subsequence problem was initially viewed as an example of a dynamic approach and its major applications include the process of aligning whole genome sequences. We are presenting an optimal solution for the LIS problem using a modified divide-and-conquer approach with o(n log n) time complexity. The proposed method is more efficient and simpler than the earlier LIS solutions using D&C approach. Our approach does not require sorted data and it is more efficient and better than a sequential approach as we can solve the problem by dividing it into smaller subproblems. During the division phase, we do not need any prior knowledge about the length of the LIS - the division process is simple and is independent of the type and range of the input sequence and the |LIS|. We have implemented the proposed approach in 'C' language using input sequences of different lengths ranging from 10 to 100,000 elements.

Keywords: LIS; longest increasing subsequence; MD&C; modified divide-and-conquer; FRYT; first row of Young Tableaux; FSP¹; first subproblem; SSP²; second sub-problem.

DOI: 10.1504/IJAIP.2024.142666

International Journal of Advanced Intelligence Paradigms, 2024 Vol.29 No.2/3, pp.170 - 195

Received: 27 Mar 2019
Accepted: 20 Jun 2019
Published online: 15 Nov 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article