Longest Increasing Subsequence

Given an unsorted array. Find 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: [5,7,13,17]
    LIS is [5,7,13,17] of length 4.

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

Algorithm:

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

a. We create an auxiliary vector, if we use vector as inputor auxiliary array, if we use array as input.

b. In this array,
    1) If current is greater than last element of auxiliary vector, then append the element.
    2) If current is smaller than last element of auxiliary vector, then replace the element.

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

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

e. Create an array to store the indexes and previous indexes while appending and replacing into the auxiliary vector.

f. Finally print them using indices vector.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;


// Binary search
int Binary_search(int array[], vector<int> &v, int left, int right, int index)
{
    while (right-left > 1) 
    {
        int mid = left + (right-left)/2;
        if(array[v[mid]] < index)
        {
            left = mid;
        }
        else
        {
            right = mid;
        }
    }
    return right;
}
//function to print LIS
int LIS(int array[], int n)
{

    vector<int> Indices(n, 0); 
    vector<int> previousIndices(n, -1);
 
    int length = 1;
    for (int i = 1; i < n; i++)
    {
        if (array[i] < array[Indices[0]])
        {
            Indices[0] = i;
        }
        //append element
        //store indices and previous indices
        else if (array[i] > array[Indices[length-1]])
        {
            previousIndices[i] = Indices[length-1];
            Indices[length++] = i;
        }
        //replace element
        //update prev
        //update indices and previous indices 
        else
        {
            int pos = Binary_search(array, Indices, -1,length-1, array[i]);
 
            previousIndices[i] = Indices[pos-1];
            Indices[pos] = i;

        }
    }
    //print the LIS
    cout << "LIS is :" << endl;
    for (int i = Indices[length-1]; i >= 0; i = previousIndices[i])
    {
        cout << array[i] << " ";
    }
    cout << endl;
 
    return length;
}
 
int main()
{
    int array[] = {5,8,7,15,13,19,17};
    int n = sizeof(array)/sizeof(array[0]);
    cout<<"LIS Length is: "<<LIS(array, n); 
    return 0;
}
Try It


Next > < Prev
Scroll to Top