# Longest Increasing Subsequence

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of `LIS`

for `[50, 3, 10, 7, 40, 80]`

is `4`

and `LIS`

is `[3, 7, 40, 80]`

.

#### Example 1:

Input | 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
---|---|---|---|---|---|---|---|---|

`LIS` | `1` | `2` | `3` | `4` | ||||

Output | 4 |

#### Example 2:

Input | 10 | 22 | 9 | 33 | 21 | 50 | 41 | 60 | 80 |
---|---|---|---|---|---|---|---|---|---|

`LIS` | `1` | `2` | `3` | `4` | `5` | `6` | |||

Output | 6 |

Note:

- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.

**Follow up: **Could you improve it to O(n log n) time complexity?

## Try it yourself

Loading full content...