**Longest Increasing Subsequence**

#### Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

There may be more than one LIS combination, it is only necessary for you to return the length.Your algorithm should run in O(n^2) complexity.*Follow up* : Could you improve it to O(n log n) time complexity?

First, We need to make one thing clear, what is the subsequence of a string, this is not the same as I first thought about it, which is actually the substring of string. So what is the subsequence of a string?

Given string `s = "abcde"`

, `l = [1, 2, 3, 4]`

`Substring`

: Must be continuous sequence.`e.g. subString = 'abc', subArray = [1, 2, 3]`

`Subsequence`

: By removing some elements from the original string. Do not have to be continuous.`e.g. subSeq = 'ace', subSeq = [1, 3, 4]`

#### Example

1 | Input: [10, 9, 2, 5, 3, 7, 101, 18] |

#### Solution

##### Dynamic Programming

If this is your first time knowing dynamic programming, it would be better to find a simpler problem to get to know DP. When you understand the principle behind it, you will find it really powerful. For this problem, we first define a list `dp`

, while `dp[i]`

means the longest subsequence ending with the i^{th} character. Then we can come up with the following formular.

`dp[i] = max(dp[j]) + 1 for j from 0 to i`

###### Algorithm

*Python*

1 | def lengthOfLIS(self, nums): |

###### Complexity

- Time Complexity: O(N^2)
- Space Complexity: O(N).

##### DP with Binary Search

The second solution might be harder to understand. I spent an hour try to understand it. Finally I figured it out. And that’s the reason I want to write this problem down, it’s a really good solution. I don’t know whether I could make you understand, but I will try my best.

Given an input list `nums = [1, 3, 2, 5]`

. Let’s define a list `tails`

that has the smallest increasing sequence through 0 to i, initializing `tail = [0, 0, 0, 0], length = 0`

. First we can think if we have already stored current increasing sequence like `tail = [1, 3, 0, 0]`

, so `tail[1] = 3`

, when `i = 2`

, we can lower the bar of the current last element of tail with `nums[2] = 2`

, so we need to update `tail[1] = 2`

, in this way, we may make more increasing sequence with current tail, `length`

stays the same, `length = 2`

. And when `i = 3`

, `nums[3] = 5`

, which is larger than the last element in `tail`

, so we can add this one into our `tail`

list, so the last element in `tail`

would be `tail[2] = 5`

, and then the length of `tail`

would be the longest subsequence.

So the basic idea of this solution is following:

`length`

is the index of next of current last element in `tail`

, `x`

is the current num in `nums`

.

1 | if x > tail[length]`: tail[length] = x, and length++ |

If you understand the above part, **Congratulations~** Next we will combine with binary search to make the time complexity `O(nlogn)`

. And this is the most tricky part.

We want to find the right position for `x`

, and in `tail`

, all elements are increasing order, so we come up with the binary search. The detailed code can be found in the following algorithm. Please be careful with the *border* element.

###### Algorithm

*Python*

1 | def lengthOfLIS(self, nums): |

###### Complexity

- Time Complexity: O(NlogN)
- Space Complexity: O(N).

This solution is so long but the code is clear, hope you could understand. If there is something wrong, please let me know. And if you still could not understand, you can refer to this [link](https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824). Maybe this one is detailed and easier to understand.