Improvised divide and conquer approach for the LIS problem

There exist many optimal (using single and multiple processors) and approximate solutions to the longest increasing subsequence (LIS) problem. Through this paper, we present the enhancement to the divide-and-conquer approach presented in paper [1]. An improved D&C algorithmic solution is proposed which outputs optimal solution in all cases. The proposed algorithm takes O(nlog⁡n) time in best and average cases and o(nlog2⁡n) time in worst case. The portion of the proposed solution can run in parallel using multiprocessors.