In this article, you will learn to resolve the longest increasing subsequence problems by using a dynamic programming algorithm

A longest increasing subsequence is obtained from a sequence, has elements in increasing order and as long as possible

## Problem 1

Given an unsorted array of numbers

`a`

Write an algorithm to find the length of the longest increasing subsequence (LIS)

The LIS does not necessarily have to be contiguous or unique

### Example 1.1

Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Output: 6

Explanation: The LIS is {0, 2, 6, 9, 11, 15}. It's not contiguous or unique. Other instances are {0, 2, 6, 9, 13, 15}, {0, 4, 6, 9, 11, 15, {0, 4, 6, 9, 13, 15}

### Approach 1.1: Brute force with recursion

Using recursion to scan the increasing subsequences of all elements in the given array to find the length of the longest one

At each iteration, there are two options: count or not the current element based on its value is greater than the previous element or not, respectively

```
```

- Output

```
6
```

Time complexity: O(2

^{n}) as you have to iterate over all elements in the array and each element has 2 optionsSpace complexity: O(1)

### Approach 1.2: Dynamic programming

Optimal substructure and overlapping subproblems: say lis

_{i}, lis_{j}are length of the LIS at index i and jlis

_{i}= max(lis_{i}, lis_{j}+ 1), ∀0 <= j < i and a[i] > a[j]Use an array

`cache[n]`

to cache the length of the LIS at each index corresponding with the given array`a[n]`

Bottom-up filling

`cache[n]`

with the base casecache[i] = 1, ∀0 <= i < n

LIS(a[n]) = max(cache[n])

```
```

- Output

```
6
```

Time complexity: O(n

^{2}) as you use 2 for-loopSpace complexity: O(n) as you use a cache array which has the same size as the given array

## Problem 2

Given an unsorted array of numbers

`a`

Write an algorithm to find the longest increasing subsequence (LIS)

The LIS does not necessarily have to be contiguous or unique

### Example 2.1

Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Output: [0, 2, 6, 9, 11, 15]

Explanation: The LIS is {0, 2, 6, 9, 11, 15}. It's not contiguous or unique. Other instances are {0, 2, 6, 9, 13, 15}, {0, 4, 6, 9, 11, 15, {0, 4, 6, 9, 13, 15}

### Approach 2.1: Dynamic programming

- Optimal substructure and overlapping subproblems same as the previous approach of problem 1

```
```

- Output

```
[0, 2, 6, 9, 11, 15]
```

Time complexity: O(n

^{2}) as you use 2 for-loopSpace complexity: O(n

^{2}) as you use 2D array to cache the increasing subsequences