Leetcode 300 Solution

This article provides solution to leetcode question 300 (longest-increasing-subsequence)
Categories:
Tags:
Access this page by simply typing in "lcs 300" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/longest-increasing-subsequence

Solution

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []

        for i, num in enumerate(nums):
            l = 0
            r = len(dp)

            while l < r:
                m = (l + r) // 2
                if dp[m] >= num:
                    r = m
                else:
                    l = m + 1

            if l == len(dp):
                dp.append(num)
            else:
                dp[l] = num

        return len(dp)