> For the complete documentation index, see [llms.txt](https://liuzhenglaichn.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuzhenglaichn.gitbook.io/algorithm/longest-increasing-subsequence.md).

# Longest Increasing Subsequence

Find the longest increasing subsequence from an array of numbers.

Example:

```
A = [10,9,2,5,3,7,101,18]
LIS = [2,3,7,101]
```

The optimal solution is a DP + binary search solution with time complexity `O(NlogN)` and space complexity `O(N)`.

## Problems

* [300. Longest Increasing Subsequence (Medium)](https://leetcode.com/problems/longest-increasing-subsequence/)
* [1671. Minimum Number of Removals to Make Mountain Array (Hard)](https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/): a great bidirectional extension of this problem.