Longest increasing subsequence

Contents:

1. Wtf is Longest increasing subsequence?
2. Dynamic programming approach to find the length.
3. O(nlog(n)) solution to find length using binary search.

Longest Increasing Subsequence:

Suppose we are given an array of integers and a subsequence is a sequence of numbers we get after removing some elements from the array. So as the name suggests a longest increasing subsequence(LIS) is the longest sequence of array elements that we can get after removing some integers from the array and remaining elements must be in increasing order.

Eg. Array a[] = {1, 2, 4, 3, 6}

Here, we can get longest increasing subsequence by removing 4 from the array.

LIS = {1, 2, 3, 6}.

Dynamic Programming Solution:

Problem: Given an array of integers, find the length of LIS?

Let a[] is the given array of integers.

Let dp[] be the new array, where dp[i] gives the length of LIS considering the ith element of array a[] as the last element of LIS. Initialize this dp[] with 1 because the length of LIS is obviously at least 1.

Now suppose we already calculated dp[] from index 0 to i-1. Now we need to calculate dp[i].

To calculate dp[i] we need to see if there is some a[j] < a[i] where j ranges from (0, i-1).

If some a[j] < a[i] then we can say that dp[i] = max(dp[i], dp[j]+1). Why?

Because dp[j] gives us the length of LIS considering a[j] as last element of LIS and we know that a[j] < a[i], so that's why if we consider a[i] as last element of LIS and a[j] as second last element then clearly dp[i] can be maximum of dp[i] or dp[j]+1. Before doing dp[i] = max(dp[i], dp[j]+1), dp[i] gives the length of LIS considering a[i] as last element of LIS and 2nd last element of LIS is something other than a[j].

In this way, we calculate dp[] and the maximum value of this array gives the length of LIS.

Implementation in C++:

#include<bits/stdc++.h>

using namespace std;

int main(){
 int n; // length of array a
 cin >> n;
 int a[n]; // input array
 for(int i = 0 ; i < n ; i++){
  cin >> a[i];
 }
 int dp[n]; // dp array
 for(int i = 0; i < n; i++)
  dp[i] = 1;  // initializing dp[] with 1
 int answer = 1;
 for(int i = 1 ; i < n ; i++){
  // considering ith element as last element of LIS
  for(int j = 0 ; j < i ; j++){
   if(a[j] < a[i]){
    dp[i] = max(dp[i], dp[j] + 1);
   }
  }
  answer = max(answer, dp[i]);
 }
 cout << "Length of LIS is : " << answer << endl;
}

Time Complexity: O(n*n)

O(nlog(n)) Solution: 

We can also find the length of LIS in O(nlog(n)) using binary search and a temporary array.

We will use a temporary vector v[] which will always be sorted and its last element gives the last element of LIS.

So let's iterate the given array a[] from the index 0 to (n-1). 

If v[] is empty directly push the a[i] to v.

If last element of LIS till now i.e. v[last_idx] is smaller than current element i.e. a[i], push a[i] into the vector v.

Otherwise we need to search the position where a[i] can be placed in vector v, in such a way that it does not disturb the current length of LIS which is length of vector v. We can find the suitable position by doing binary search over the vector v or using upper_bound().
Finally length of vector v will give the length of LIS.
Let's take an example.

a[] = {12, 13, 2, 15, 4, 5, 6}

v[] = {}

- - - - - - - - - - 

idx = 0 // index of current iteration

v is empty so push a[idx] in v.

v[] = {12}

last_idx = 0 // last index of v

- - - - - - - - - -

idx = 1

v[last_idx] < a[idx]

push a[idx] in v.

v[] = {12, 13}

last_idx = 1

Till now we have maximum length LIS is 2.

- - - - - - - - - -

idx = 2

v[last_idx] >  a[idx] (13 > 2)

Find the first position in v[] where v[pos] > a[idx]

clearly, pos = 0

v[] = {2, 13}

last_idx = 1

- - - - - - - - - -

idx = 3

v[last_idx] < a[idx] (13 < 15)

push a[idx] in v.

v[] = {2, 13, 15}

last_idx = 2

Till now we have maximum length LIS is 3.

- - - - - - - - - -

idx = 4

v[last_idx] >  a[idx] (15 > 4)

Find the first position in v[] where v[pos] > a[idx]

clearly, pos =1

v[] = {2, 4, 15}

last_idx = 2

- - - - - - - - - -

idx = 5

v[last_idx] >  a[idx] (15 > 5)

Find the first position in v[] where v[pos] > a[idx]

clearly, pos =2

v[] = {2, 4, 5}

last_idx = 2

- - - - - - - - - -

idx = 6

v[last_idx] <  a[idx] (5 < 6)

push a[i] in v.

v[] = {2, 4, 5, 6}

last_idx = 3

Till now we have maximum length LIS is 4.

Length of LIS = 4

Bravo !! This is like magic. xD

Note : If there are many LIS of same size then the last element of vector v, will always give the last element of that LIS which has the smallest last element.

Implementation in C++:

#include<bits/stdc++.h>

using namespace std;

int main(){
 int n; // length of array a
 cin >> n;
 int a[n]; // input array
 for(int i = 0 ; i < n ; i++){
  cin >> a[i];
 }
 vector<int> v;
 for(int i = 0 ; i < n ; i ++){
  // push if v is empty of v[last_idx] < a[i]
  if(v.empty() or v.back() < a[i]){
   v.push_back(a[i]);
  }else{
   // binary search the position
   int pos = upper_bound(v.begin(), v.end(), a[i]-1) - v.begin();
   v[pos] = a[i];
  }
 }
 // size of vector v will give the length of LIS
 cout << "Length of LIS : " << v.size() << endl;
}

Problem for practice: Try to find the length of longest non-decreasing subsequence. (Hint : note the difference, xD)

Thank You!
Happy Coding.