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 2n.
nC0 + nC1 + nC2 + … + nCn = 2n

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 the element at position ‘b’ > the 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
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 : O ( N 2 ), where ‘N’ is the number of elements in the sequence.



Longest increasing subsequence implementation

def Longest_Increasing_Subsequence (seq):

    num_elements = len(seq)

    # Create a list of list
    sequence_list = [[] for i in range (len(seq))]

    sequence_list[0].append(seq[0])

    for b in range(1, num_elements):

        for a in range(0, b): 

            if (seq[b] > seq[a] and (len(sequence_list[b]) < len(sequence_list[a]))):

                # Copy the previously found longest increasing subsequence at current position (b)
                # before appending the current element
                # Copying one list into another
                sequence_list[b] = list(sequence_list[a]) 

        # Appending the current element at position 'b' to the subsequence
        sequence_list[b].append(seq[b])

    print("\nGiven sequence...")
    for num in seq:
        print(str(num) + " ", end='')

    max_len = 0;
    print("\nLongest increasing subsequences generated at positions");
    cnt = 0 
    for seq in sequence_list:
        print("[" + str(cnt) + "]: " + str(seq))
        max_len = max( max_len, len(seq))
        cnt += 1
    print("Maximum length of increasing subsequence: " + str(max_len) + "\n")

def main():

    sequence = [3, 2, 6, 4, 5, 1, 7]
    Longest_Increasing_Subsequence (sequence)

    sequence.clear()

    sequence = [2, 2, 3, 2, 2, 1, 2, 3]
    Longest_Increasing_Subsequence (sequence)

if __name__ == "__main__":
    main()

Output

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
#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

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
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;

class LIS {

    public void Longest_Increasing_Subsequence (List<Integer> seq) {

        int sz = seq.size();

        List<List<Integer>> seq_list;

        seq_list = new ArrayList<>(sz);
        for (int i=0; i<sz; i++) {
            seq_list.add(new ArrayList<Integer>(sz));
        }

        seq_list.get(0).add(seq.get(0));

        for (int b=1; b<sz; b++) {

            for (int a=0; a<b; a++) {

                if ( seq.get(b) > seq.get(a) && (seq_list.get(b).size() < seq_list.get(a).size()) ) {
                    /* Copy the previously found longest increasing subsequence at current position
                       before appending the current element */
                     seq_list.get(b).clear();
                     for (Integer i : seq_list.get(a)) {
                         seq_list.get(b).add(i);
                     }
                }
            }
            // Appending the current element to the subsequence
            seq_list.get(b).add(seq.get(b));
        }

        System.out.println("Given sequence...");
        for(Integer i : seq)
            System.out.print(i + " ");

        int max_len = 0;

        System.out.println("\nLongest increasing subsequences generated at positions");

        for (int i=0; i<sz; i++) {
            System.out.print("[" + i + "]: ");
            max_len = Math.max(max_len, seq_list.get(i).size());
            for (Integer p : seq_list.get(i)) {
                System.out.print(p + " ");
            }
            System.out.println();
        }
        System.out.println("Maximum length of increasing subsequence: " + max_len + "\n");
    }

    public static void main(String args[]) {

        LIS seq = new LIS();

        List<Integer> sequence1 = Arrays.asList(3, 2, 6, 4, 5, 1, 7);
        seq.Longest_Increasing_Subsequence (sequence1);

        List<Integer> sequence2 = Arrays.asList(2, 2, 3, 2, 2, 1, 2, 3);
        seq.Longest_Increasing_Subsequence (sequence2);
    }
}

Output

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



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.