Longest Increasing Subsequence in O(nlogn)

Today we are going to discuss longest increasing subsequence of an array using efficient algorithm with O(nlogn) complexity.

As we all know lis can also be solved by dynamic programming paradigm but that algorithm take O(n^2) time.

Let assume that arr[i] is input array from i = 0 to n

Let S[i] be defined as the smallest integer that ends an increasing sequence of length i.

Now iterate through every integer X of the input set arr[] and do the following:

1) If X > last element in S, then append X to the end of S. This essentially means we have found a new largest LIS.

2) Otherwise find the smallest element in S, which is greater then or equal ( >= ) to X, and change it to X. Because S is sorted at any time, the element can be found using binary search in log(N).

So, total runtime – N integers and a binary search for each of them – N * log(N) = O(N log N)

Now let’s understand above algorithm using real example:

Set of integers: 2 6 3 4 1 2 7 9 5 8
Just iterate through each integer in above array.

Steps:

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 7} - New Largest LIS
8. S = {1, 2, 4, 7, 9} - New largest LIS
9. S = {1, 2, 4, 5, 9} - Changed 7 to 5
10. S = {1, 2, 4, 5, 8} - Changed 8 to 9

So the length of the LIS is 5 (the size of S).

Above algorithm is used to find length of LIS. To print the actual elements of LIS let’s modify algorithm to find the length and element of LIS.

To reconstruct the actual LIS we will use a parent[] array of length equal to input array. Where parent[i] be the predecessor of element with index i in the LIS ending at element with index i.

Also in the array S, we will not keep the actual integers, but their indices(positions) in the set. We do not keep {1, 2, 4, 5, 8}, but keep{4, 5, 3, 8, 9}.
2 6 3 4 1 2 7 9 5 8
So how do we update array parent[] let’s look at the above two points again:

Iterate through each element X of an input array arr[]
1) If X > last element in S, then parent[indexOfX] = LastElementOfS. This means the parent of the newest element is the last element of array S and then we will just prepend X to the end of S.

2) Otherwise find the index of the smallest element in S, which is >=than X, and change it to X. Here parent[indexOfX] = S[index – 1].

Here is a commented c++ program so go through each line one by one and let me know in case there is any doubt.

#include <iostream>
using namespace std;
//! @author : Rajul
//! code is poetry
 
//Program to find longest Increasing Subsequence in nlog(n) time
 
//! Function to do ceil binary search
//! Usage: To return either position of search's value or position of smallest
//! elememt in array which is greater then value of search
//! Here n = size of array small
int BinarySearch(int *arr,int *small,int n, int value)
{
   int low = 0;
   int high = n-1;
   int mid;
   while (low < high)
   {
       mid = low + ((high - low) / 2);
       //! if array's mid value is greater then search value then select
       //! high as mid , this is where we are making it a ceil binary search
       if (arr[small[mid]] > value)
           high = mid;
       else if (arr[small[mid]] < value)
           low = mid + 1;
       else
           return mid;// found
   }
   return low;// not found
}
 
//! function to print longest Increasing Subsequence with nlog(n) complexity
int LIS(int *arr, int n)
{
    int *small = new int[n];
    int *parent = new int[n];
    int size = 0;
    for(int i=0 ; i<n ;i++)
    {
        if(i == 0)
        {
            small[size] = i;
            parent[i] = -1;
        }
        //! Find the "index" of the smallest element in array small, which is >=than X,
        //! and change it to X. Here parent[indexOfX] = S[index - 1].
        else if(arr[i] <= arr[small[size]])
        {
            int pos = BinarySearch(arr,small,size+1,arr[i]);
            small[pos] = i;
            if(pos != 0)
            {
                 parent[i] = small[pos-1];
            }
    	}
        //! parent[indexOfX] = Last Element Of S
        else
        {
            size = size+1;
            small[size] = i;
            parent[i] = small[size-1];
        }
    }
    cout<<"Length of Longest Increasing Subsequence = "<<size+1<<endl;
 
    int pos = small[size];
    //! print Longest Increasing Subsequence
    while(size >=0)
    {
        cout<<arr[pos]<<endl;
        pos = parent[pos];
        size--;
    }
}
 
int main( )
{
    int arr[] = {99, -7, 10, 9, 2, 3, 8, 8, 1, 2, 3};
    unsigned int size = sizeof(arr)/sizeof(int);
    LIS(arr,size);
    return 0;
}

Github Gist Link

 

Site Footer