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

*1*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.*

Our answer will be the biggest element in the *dp* array. The overall complexity of this code is O(N^{2}).

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 *v * 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 *v * which in this case is *7. * The total time complexity of this approach is NlogN.

Amazing explanation! Was looking for this since forever but couldn’t find a decent article until now!