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)**

- LIS at position 0 is the first element of the sequence.
- For current position ‘b’ from 1 upto N
- For previous position ‘a’ from 0 upto b
- 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'
- LIS for position ‘b’ has been found

Copy longest subsequence at position ‘a’ into ‘b’. - 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 | 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 of finding longest increasing subsequence using dynamic programming : O(N^2)**, where ‘N’ is the number of elements in the sequence.

**Java**

Java : Finding the longest increasing subsequence

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

**Python**

Python: Program for finding the longest increasing subsequence.

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

**C++ : Program for finding the longest increasing subsequence**

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

All rights reserved.