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

300. Longest Increasing Subsequence

DP solution

# time complexity: O(n^2)
# Space complexity: O(n)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1]*len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    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 [1] and [2] (In Chinese).

Thanks for reading.

Reference

[1]https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation

[2]https://www.luogu.com.cn/blog/pzk/zui-zhang-sheng