[LeetCode][Python]300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=daily-question&envId=2024-01-05

Longest Increasing Subsequence - LeetCode

List가 주어졌을때, List에서 숫자가 오름차순 중에서 제일 긴 길이를 구하는것이다.

---

이틀 전, 이진탐색을 공부하면서 써먹을 수 있겠다는 생각이 들었다.

https://baseballgrammer.tistory.com/88

5일차 - 이진 탐색

 

Python에서는 이진탐색을 할 수 있는 라이브러리인 bisect를 사용할 수 있다.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        answer = []
        for num in nums:
            i = bisect_left(answer, num)

            if i == len(answer):
                answer.append(num)
            else:
                answer[i] = num
                
        return len(answer)