Longest Increasing Subsequence NlogN approach

In Longest Increasing Subsequence we need to find the size longest increasing array in which elements are sorted in ascending order and elements need not to be contiguous.

First we’ll see how it can be solved with dynamic programming approach.

Below are the illustrations 

This is our given array  arr = [5,1,2,2,1,9,2,4,7,8]

In first step we’ll take another array to store our dp array with all zeros dp =  [0,0,0,0,0,0,0,0,0,0] 

Initializing dp[0] = 1

Then we’ll  iterate over the array from arr[1] to arr[n – 1] 

for(int i = 1; i < n; i++){  // initializing form 1 as at dp[0] = 1
dp[i] = 1;
//forloop for iterating going backwards
mex = 0; // mex variable to keep track of max value in dp while moving backwards

for(int j = i - 1; j >= 0; j--){ // reverse for loop

if(arr[i] >= arr[j]){
mex = max(mex, dp[j]);// this will give us max dp value as we're finding longest increasing subsequesnce
}
}
// As we got out max value we'll add it to our dp array
dp[i] += mex;

}

 

At ever point we’ll check if there is any number smaller then or equal to current element arr[i]  from th  to 0 index backwards.
In the case below we checked if there is any number smaller then or equal to arr[1]  there is none so we keep 1 in dp array. When i = 2  we check if there is any number smaller then or equal to arr[i]  yes there is 1 so we take the corresponding value of 1 in dp table which is also so we add 1 to dp[i] += 1 and since we initialized dp[i] = 1  now the value of dp[i] becomes 2. 

And when i = 3  then we move back and find 2 which is equal to arr[i]  and with maximum corresponding value in the dp array so we take the corresponding dp value of 2 which was 2.  Which make it dp[i] += 2 = dp[i] = 3.

Similarly filling the dp array as shown in the picture below

Our answer will be the biggest element in the dp array. The overall complexity of this code is O(N2).
This can be improved to NlogN with binary search.

Here’s how binary search will be used to in this problem

For binary search to work we need to have a sorted array. 

So, first we’ll make a temporary vector as we can increase the size of vectors. v = [].

We’ll take the first element and push it in vector v  then we’ll take the element at i = 1  and check if the last element of vector is smaller/equal or greater then current element i.e arr[i]. In this case it is greater so we find the smallest element in the vector which is greater then  arr[i]. 

so we will do a binary search from 0 to i – 1 element.

In the case below it is number 5 so we will replace 5 with number 1.  Moving on to i = 2 we see arr[2] = 2 which is greater then last element of vector in this case we’ll simply push it at the end of vector.  v = [1,2] .

Moving on we see the next element for i = 3, arr[i]  is 2  which is equal or greater then last element in vector v so we simply push it in vector. Now, v = [1,2,2].

In the next element in the case below when i = 4, arr[i] = 1 is smaller then last element in vector so we’ll again find the smallest element in the vector which is greater then 1 as the vector is already sorted we can apply binary search to find that element in logn time. In this case it is 2 so we replace 2 with 1.  

For  i = 5  it is greater then last element in vector so we push it at the back of vector without any binary search.

Now the vector is v = [1,1,2,9].

Similarly, the final vector is v = [1,1,2,2,4,7,8].

 

Now for finding Longest Increasing Subsequence all we need to do is to print the size of vector which in this case is 7.  The total time complexity of this approach is NlogN.

Related Posts

One thought on “Longest Increasing Subsequence NlogN approach

Leave a Reply

Your email address will not be published.