300. Longest Increasing Subsequence

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/longest-increasing-subsequence
• topics: Binary Search

Given an integer array nums, return the length of the longest strictly increasing subsequence

Idea

Construct the sequence using binary search

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = []
        for num in nums:
            i = bisect_left(sub, num)
 
            # If num is greater than any element in sub
            if i == len(sub):
                sub.append(num)
            
            # Otherwise, replace the element found by bisect
            else:
                sub[i] = num
        
        return len(sub)