Longest Increasing SubSequence (LIS)

Finding longest increasing subsequence (LIS)

A subsequence is a sequence obtained from another by the exclusion of a number of elements. Also, the relative order of elements in a subsequence remains the same as that of the original sequence.

Example of an increasing subsequence in a given sequence
Sequence: [ 2, 6, 3, 9, 15, 32, 31 ]
Subsequence 1: [ 2, 9, 15 ]
Subsequence 2: [ 2, 6, 31 ]
Subsequence 3: [ 3, 15, 32, 31 ]

If there are ‘n’ elements in a sequence, then the number of subsequences that can be obtained are 2^n.
nC0 + nC1 + nC2 + .. nCn = 2^n

The idea is to find for each position the longest increasing subsequence ending with the element at that position.
It is evident that the LIS for the 0’th position is the first element.


Algorithm : Longest increasing subsequence (LIS)
1. LIS at position 0 is the first element of the sequence.
2. For current position ‘b’ from 1 upto N
3.      For previous position ‘a’ from 0 upto b
4.          if element at position ‘b’ is greater than element at positions ‘a’ and size of LIS at positions ‘a’ is greater that LIS at position ‘b’
5.             LIS for position ‘b’ has been found
               Copy longest subsequence at position ‘a’ into ‘b’.
6.      Append element at position ‘b’ to the LIS at position ‘b’ i.e (LIS at position ‘a’ + element at ‘b’)


Example of finding the longest increasing subsequence in a given sequence
Consider the sequence [ 3, 2, 6 ]
The longest increasing subsequence in the above sequence is [ 3, 6 ]

Current
Position
Previous
Position
LIS at current position LIS at previous position Description
0 None [ 3 ] None It is obvious that the longest increasing subsequence at position 0 is [ 3 ].
1 0 None
Created sequence : [ 2 ]
[ 3 ] Element ‘2’ at the current position 1 is smaller than the element ‘3’ at the previous position 0. ‘2’ cannot be appended to the subsequence [ 3 ] at position 0.
Thus the LIS now created at the current position 1 is [ 2 ].
2 0 None
Created sequence : [ 2, 3 ]
[ 3 ] Element ‘6’ at the current position 2 is greater than the element ‘3’ at the previous position 0 and no subsequence has yet been found yet for position 2.
Thus the LIS now created at the current position 2 is [ subsequence at position 0 + element at position 2 ]. i.e [ 3 ] + ‘6’ i.e [ 3, 6 ].
2 1 [ 3, 6 ] [ 2 ] Element ‘6’ at position 2 is greater than element ‘2’ (at previous position 1) but a subsequence [ 3, 6 ] has already been found for position 2 of length 2 greater than the subsequence at position 1 i.e [2], thus longest increasing subsequence at position 2 remains the same as [ 3, 6 ].


Data structure used for storing subsequences : list of lists
Time complexity of finding longest increasing subsequence using dynamic programming : O(N^2), where ‘N’ is the number of elements in the sequence.


C++14 implementation of longest increasing subsequence using dynamic programming.

#include<iostream>
#include<vector>

using namespace std;

class LIS {

    public:
    void Longest_Increasing_Subsequence (vector<int> & seq) {

        int num_elements = seq.size();
        vector<vector<int>> vec_sequences (num_elements); 

        vec_sequences[0].push_back(seq[0]);

        for (int b=1; b<num_elements; b++) {
            for (int a=0; a<b; a++) {
                if ( seq[b] > seq[a] and (vec_sequences[b].size() < vec_sequences[a].size()) ) {
                   /* Copy the previously found longest increasing subsequence at current position
                      before appending the current element */
                   vec_sequences[b] = vec_sequences[a]; 
                }
            }
            // Appending the current element to the subsequence
            vec_sequences[b].push_back(seq[b]);
        }

        cout << "Given sequence " << endl;
        for(auto & itr : seq)
            cout << itr << " ";
        cout << endl;

        int max_len = 0;
        cout << "Longest increasing subsequences generated at positions" << endl;
        for (int i=0; i<num_elements; i++) {
            cout << "[" << i << "]: ";
            max_len = max( max_len, (int) vec_sequences[i].size());
            for (auto& itr: vec_sequences[i]) {
                cout << itr << " ";
            } cout << endl;
        }
        cout << "Maximum length of increasing subsequence: " << max_len << endl;
    }   
};

int main() {

    LIS seq;
    vector<int> sequence1 = {3,2,6,4,5,1,7};
    seq.Longest_Increasing_Subsequence (sequence1);

    cout << endl;
    vector<int> sequence2 = {2,2,3,2,2,1,2,3};
    seq.Longest_Increasing_Subsequence (sequence2);
    return 0;
}

Output showing the longest increasing subsequence in a given sequence

Given sequence 
3 2 6 4 5 1 7 
Longest increasing subsequences generated at positions
[0]: 3 
[1]: 2 
[2]: 3 6 
[3]: 3 4 
[4]: 3 4 5 
[5]: 1 
[6]: 3 4 5 7 
Maximum length of increasing subsequence: 4

Given sequence 
2 2 3 2 2 1 2 3 
Longest increasing subsequences generated at positions
[0]: 2 
[1]: 2 
[2]: 2 3 
[3]: 2 
[4]: 2 
[5]: 1 
[6]: 1 2 
[7]: 1 2 3 
Maximum length of increasing subsequence: 3

Reference: https://www.youtube.com/watch?v=4fQJGoeW5VE&authuser=0

Copyright © 2019, Algotree.org.
All rights reserved.