Longest Increasing Subsequence

LIS problem has a recursive solution and this also can be solved using DP.

Recursive solution:

But the solution has overlapping substructure property The same solution is calculated more than once)it can be solved using DP.

DP Solution:

Time complexity of this solution is O(N*N).

Better Solution with Time Complexity O(N*logN):

Lets assume A[] is an array of unsorted numbers. We keep track of active lists of LIS of different lengths. We only keep track of active lists of only one for each length, if we find more than one sequence of same length than we only keep the  sequence having the smallest ending numbers. To design a O(N log N) algorithm following conditions are checked.

1) If A[i] is smallest of all ending numbers of existing active list, then start a new list keeping A[i] as first element new active list of length 1;

2) If A[i] is the largest of all the ending numbers of active list then clone the  longest active list and add the number as last element.

3) If  A[i] is in between smallest and largest ending elements of active lists then find an active list having the end element smaller than A[i] ,clone that active list, add A[i] at the end of that active list and discard the previous active list.


Leave a Reply

Your email address will not be published. Required fields are marked *