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

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 , 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.append(seq)

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
: 
: 
: [3, 6]
: [3, 4]
: [3, 4, 5]
: 
: [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
: 
: 
: [2, 3]
: 
: 
: 
: [1, 2]
: [1, 2, 3]
Maximum length of increasing subsequence: 3
``````
``````#include<iostream>
#include<vector>

using namespace std;

void LIS (vector<int> & seq) {

int N = seq.size();
vector<vector<int>> subseqs (N);

subseqs.push_back(seq);

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

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<N; i++) {
cout << "[" << i << "]: ";
max_len = max( max_len, (int) subseqs[i].size());
for (auto& itr: subseqs[i]) {
cout << itr << " ";
} cout << endl;
}
cout << "Maximum length of increasing subsequence: " << max_len << endl;
}

int main() {

vector<int> seq1 = {3,2,6,4,5,1,7};
LIS (seq1);

cout << endl;
vector<int> seq2 = {2,2,3,2,2,1,2,3};
LIS (seq2);
return 0;
}
``````

Output

``````Given sequence
3 2 6 4 5 1 7
Longest increasing subsequences generated at positions
: 3
: 2
: 3 6
: 3 4
: 3 4 5
: 1
: 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
: 2
: 2
: 2 3
: 2
: 2
: 1
: 1 2
: 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++) {
}

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)) {
}
}
}
// Appending the current element to the subsequence
}

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
: 3
: 2
: 3 6
: 3 4
: 3 4 5
: 1
: 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
: 2
: 2
: 2 3
: 2
: 2
: 1
: 1 2
: 1 2 3
Maximum length of increasing subsequence: 3
``````

Copyright (c) 2019-2022, Algotree.org.