Length of Longest Increasing Subsequence

Given an unsorted array. Find the length of the longest increasing subsequence in the given array.

A subsequence is a part of an array which is sequence that is derived from another sequence by deleting some elements without changing the order.

Example

a) Input array: [5, 8, 7, 15, 13, 19, 17]
Output: 4
LIS is [5,7,13,17]

b) Input array: [23, 20, 17, 9, 11, 7]
Output: 2
LIS is [9, 11]

Algorithm

Time complexity: O(NlogN), N is size of the array.

1. We create an auxiliary vector if we use vector, or auxiliary array if we use array.

2. In this array,

       a. If current is greater than last element of auxiliary vector, then append the element.

       b. If current is smaller than last element of auxiliary vector, then replace the element.

3. Finally, print the length of auxiliary array which is length of longest increasing subsequence.

4. For replacing the element, we use binary search to find the element in auxiliary array and replace it.

Algorithm working

C++ Program

//LIS longest increasing subsequence
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

int Binary_search(vector<int> &v, int left, int right, int index)
{
    while (right-left > 1) 
    {
        int mid = left + (right-left)/2;
        if(v[mid] < index)
        {
            left = mid;
        }
        else
        {
            right = mid;
        }
    }
    return right;
}
 
int LISlen(vector<int> &v) 
{
    if(v.size() == 0)
    {
        return 0;
    }
    vector<int> aux_vector(v.size(), 0);
    int length = 1;
    aux_vector[0] = v[0];
    for (size_t i = 1; i < v.size(); i++)
    {
        if (v[i] < aux_vector[0])
        {
            aux_vector[0] = v[i];
        }
        //append element
        else if (v[i] > aux_vector[length-1])
        {
            aux_vector[length++] = v[i];
        }
        //find index by binary search
        //replace element
        else
        {
            aux_vector[Binary_search(aux_vector,-1,length-1,v[i])] = v[i];
        }
    }
 
    return length;
}
 
int main() {
    const size_t N = 9;
    int a[N] = {3, 1, 5, 2, 6, 4, 9};
    vector<int> v( a, a + N );
    cout << "length of LIS is" << LISlen(v) << '\n';
   return 0;
}
Try It


Next > < Prev
Scroll to Top