### What is Subsequence?

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence {A, B, D} is a subsequence of {A, B, C, D, E, F} obtained after removal of elements C, E, and F.

### What is Longest Increasing Subsequence (LIS)?

The increasing subsequences of array {3, 2, 6, 4, 5, 1} are {3, 6}, {2, 6}, {2, 4, 5}, and {1}. The longest is {2, 4, 5}.

### Problem

Find the longest subsequence in a given unsorted array of integers such that all elements of the subsequence are sorted in ascending order. For example, the longest increasing subsequence of {3, 2, 6, 4, 5, 1} is {2, 4, 5}.

### Approach

**Find the longest increasing subsequence of a given array**

```
```

Time complexity: O(n^{2})

Space complexity: O(n)

**Find only the length of the longest increasing subsequence of a given array**

```
```

Time complexity: O(n^{2})

Space complexity: O(n)