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)
Example Consider the sequence [ 3, 2, 6 ] The longest increasing subsequence in the above sequence is [ 3, 6 ]
| CurrentPosition | PreviousPosition | 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 | NoneCreated 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 | NoneCreated 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;
void LIS (vector<int> & seq) {
int N = seq.size();
vector<vector<int>> subseqs (N);
subseqs[0].push_back(seq[0]);
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
[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