Longest Increasing Subsequence
In this post I will go through O(nlogn) solution for Longest Increasing Subsequence whose normal execution time is O(n2)
Problem description:
Given an unsorted array of integers, find the length of longest increasing subsequence.
Solution :
Lets take an array such as [10, 9, 2, 5, 3, 7, 101, 18]
The main issue with this problem is it is unsorted had it been sorted one could have just found out longest increasing subsequence by checking if an element at position x is greater than its predecessor element if that is true you just increase the longest increasing subsequence found at x — 1 by 1
So what can we do to facilitate this issue. Lets keep account of the smallest ending element of all sequence found thus so if we have two sequences of length 1 one ending with 3 and the other ending with 5 we would keep track of 3. Similarly we will keep track of sequences of length 2 , 3 and so on
Now here is an interesting observation The array thus maintained which we contain all the smallest ending element would be always sorted. This is because if an element is part of subsequence of length i and it is smaller than any of the last element of length i — 1, i -2 and so on . The new element would be the smallest ending element of subsequence i — 1 or i -2 and so on . So according to the definition it should always be sorted
Now once we have that array we seek to find the position(p) of new incoming element in the array such that array[p-1] ≤ element <array[p+1]
Once we have this we would append element to the p-1 position increasing its length by 1 and updating array[p+1] = element
if there is no such p + 1 that is element is greater than all the element it is added at the end
if the element is smaller than all the element array[0] == element
Since searching for p can be done 0(logn) the whole operation can be done in 0(nlongn) time