The O(NLog(N)) Recursive DP Approach To Finding the Longest Increasing Subsequence (LIS)
Explanation
This algorithm involves creating a tree with node format as (a,b).
a represents the next element we are considering appending to the valid subsequence so far.
b represents the starting index of the remaining subarray that the next decision will be made from if a gets appended to the end of the subarray we have so far.
Algorithm
We start with an invalid root (INT_MIN,0), pointing at index zero of the array since subsequence is empty at this point, i.e.
b = 0.Base Case: return1ifb >= array.length.Loop through all the elements in the array from the
bindex to the end of the array, i.ei = b ... array.length-1. i) If an element,array[i]isgreater thanthe currenta, it is qualified to be considered as one of the elements to be appended to the subsequence we have so far. ii) Recurse into the node(array[i],b+1), whereais the element we encountered in2(i)which is qualified to be appended to the subsequence we have so far. Andb+1is the next index of the array to be considered. iii) Return themaxlength obtained by looping throughi = b ... array.length. In a case whereais bigger than any other element fromi = b to array.length, return1.Compute the level of the tree built as
level. Finally,level - 1is the desiredLIS. That is the number ofedgesin the longest path of the tree.
NB: The memorization part of the algorithm is left out since it's clear from the tree.
Random Example
Nodes marked x are fetched from the DB memoized values.
Java Implementation
public int lengthOfLIS(int[] nums) {
return LIS(nums,Integer.MIN_VALUE, 0,new HashMap<>()) -1;
}
public int LIS(int[] arr, int value, int nextIndex, Map<String,Integer> memo){
if(memo.containsKey(value+","+nextIndex))return memo.get(value+","+nextIndex);
if(nextIndex >= arr.length)return 1;
int max = Integer.MIN_VALUE;
for(int i=nextIndex; i<arr.length; i++){
if(arr[i] > value){
max = Math.max(max,LIS(arr,arr[i],i+1,memo));
}
}
if(max == Integer.MIN_VALUE)return 1;
max++;
memo.put(value+","+nextIndex,max);
return max;
}