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)

• 1671. Minimum Number of Removals to Make Mountain Array (Hard): a great bidirectional extension of this problem.