## Introduction

What do you understand by this term **â€˜Subsequence.â€™? **A subsequence is the sequence of an element from a given sequence such that the sequence is contiguous or non-contiguous. It will be more evident when we will start with an example. To solve this problem in O(n logn), we will be using two significant hubs of competitive programming, i.e., Binary Search and Dynamic Programming.

Binary search is a searching algorithm that follows the divide and conquer approach to search an element in a sorted array of elements in O(logn) time.

Dynamic programming is used to have problems, divided into similar sub-problems to re-use their results. Primarily, these algorithms are used for optimization.

Also Read About, __Byte Array to String__

## Problem Statement

We will be given a sequence of n numbers, and we have to find the length of the longest increasing subsequence.

Suppose you are given a sequence of n=5 elements.

Here the longest increasing subsequence is:

I.e length = 3

Let us understand the problem with one more example in detail.

Assume we are given a sequence that has [2,5,3,7,11,8,10,13,6]; letâ€™s see how our algorithm works for this subsequence.

- Initially, at the â€˜0thâ€™ index, you store â€˜2â€™ and come across as â€˜5â€™. Now you will check that if 5>2, it is so that you will insert â€˜5â€™ at index â€˜1â€™.

- Now we come across the next element, i.e., â€˜3.â€™ Now, this â€˜3â€™ is not greater than â€˜5â€™, so you will traverse and find who is the immediate next of â€˜3â€™ or â€˜3â€™ exists in this array no it doesnâ€™t exist. So the immediate next element is â€˜5â€™ and replaces this â€˜5â€™ with â€˜3â€™.

- The next element in the array after â€˜3â€™ is â€˜7â€™ and 7>3. So insert 7 in the list at the 2nd position.

- The next element in the array after â€˜7â€™ is â€˜11â€™ and 11>7, So insert 11 in the list at the 3rd position.

- Now we come across the next element, i.e., â€˜8.â€™ Now, this â€˜8â€™ is not greater than â€˜11â€™, so you will traverse and find who is the immediate next of â€˜8â€™. So the immediate next element is â€˜11â€™ and replaces this â€˜11â€™ with â€˜8â€™.

- The next element in the array after â€˜8â€™ is â€˜10â€™ and 10>8, So insert 10 in the list at the 4th position.

- The next element in the array after â€˜10â€™ is â€˜13â€™ and 13>10, So insert 13 in the list at the 5th position.

- Now we come across the next element, i.e., â€˜6.â€™ Now, this â€˜6â€™ is not greater than â€˜13â€™, so you will traverse and find who is the immediate next of â€˜6â€™. So the immediate next element is â€˜7â€™ and replaces this â€˜7â€™ with â€˜6â€™.

The number of elements that we are putting in our list is the length of the longest increasing subsequence.

**Why does this has worked?**

We store the last element of that possible sequence length; suppose you take the index from 0 to 2. This means that the subsequence length is â€˜3â€™ and at every index here takes the minimum element.