DP, Binary Search, and Monotonic queue
LIS is a very classical problem and it can be solved by using DP or binary search based on Monotonic queue.
The DP solution is so standard that everyone should be familiar with it. It has the time complexity of O(n²). The binary search based solution which is O(nlog n) is not that trivial and needs some efforts to totally master it.
Here is the problem and solution
# time complexity: O(n^2)# Space complexity: O(n)
def lengthOfLIS(self, nums: List[int]) -> int:
dp = *len(nums)
for i in range(1, len(nums)):
for j in range(i):
dp[i] = max(dp[j]+1, dp[i])
return max(dp) if dp else 0
Binary search or Monotonic queue solution can be found in  and  (In Chinese).
Thanks for reading.