### What’s a subsequence?

Any selection of items from the original array. The selection must respect the order. Meaning for `[1,2,3,4,5]`

only two of the four below are subsequences:

```
[1,2,3,4,5] ✅
[1,4,3,2,5] ❌ order not respected
[1,2,5] ✅
[5,1] ❌ order not respected
```

#### What’s the difference between a subsequence and a subarray?

Subarray, is just like subsequence, that is order must be respected. Additionally the sub-array has to be made of continuous elements.

```
[1,2,3,4,5] ✅
[1,2,3,5] ❌ gap
[1,2,3] ✅
[2,4] ❌ gap
```

### What’s a longest increasing subsequence?

This is also known as LIS.

For `[0, 3, 1, 7, 5, 2, 8]`

the longest *increasing* subsequence is: `[0,1,7,8]`

.

For `[2,2,2,2]`

. LIS is: `[2]`

.

For `[3]`

. LIS is: `[3]`

In this post, we’re only going to calculate the *length* of the LIS. We won’t construct the actual subsequence itself. To learn how to construct the path, see here

### Explanation

So this problem can be broken into subproblems i.e.

- The LIS of index 6, depends on the LIS at indices 0-5.
- The LIS of index 5, depends on the LIS at indices 0-4.
- …
- The LIS of index 1, depends on the LIS of index 0
- The LIS of index 0, is 1. Because every element has a subsequence of 1.

Whenever we can turn our problem into subproblems, then Dynamic programming is a good candidate for finding a solution.

To do this, let’s create an array named `dp`

to represent the the answer to the subproblem for a given index.

`let arr = [0, 3, 1, 7, 5, 2, 8]`

We’ll create an array with the same length of our original array. Default all the values to `1`

. Example: `var dp: [Int] = Array(repeating: 1, count: arr.count)`

.

Let’s just assume we want to calculate the LIS all the way to index `4`

. And we’ve already updated the value for all previous indexes. How do you think we need to update `dp[4]`

`[0, 3, 1, 7, 5, 2, 8]`

↑
dp[4]

Which of the following would it be?

- The value for
`dp[4]`

will be`max(dp[0] + 1, dp[1] + 1, dp[2] + 1, dp[3] + 1)`

- The value for
`dp[4]`

will be`max(dp[0] + 1, dp[1] + 1, dp[2] + 1)`

- The value for
`dp[4]`

will be`max(dp[0] + 1, dp[2] + 1)`

The correct answer is the second line.

First line is incorrect because `7`

is bigger than `5`

. `dp[3] + 1`

shouldn’t be considered.

Third line is incorrect because `1`

is smaller than `4`

, `dp[2] + 1`

should be considered.

This means that assuming there is at least one item in the array, the default value should then be `1`

.

In short:

- For every index, we use compare its value with its previous indices
- If current index is bigger, then we increase the LIS length between the two indices.
- At any given index we perform a
`max`

between all nodes that were able to increase the subsequence to that point.

- We do this till the end of the array.
- Then do a max against our dp array.

#### Pro tip

Use a **paper** and go through this example again by yourself.
Just compare any two indexes, add to the previous, do a max.
I was then able to reason with it a lot lot easier on paper.
Here’s what I wrote:

#### Code

```
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp: [Int] = Array(repeating: 1, count: nums.count)
for i in 0...nums.count - 1 {
for j in 0..<i {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
return dp.max()!
}
```

### Other Questions that use LIS:

Russian Doll - Envelopes. I plan on posting about it next.