Problem :

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


My Solution :

class Solution:
def lengthOfLIS(self, nums: 'List[int]') -> 'int':
lis = nums[:1]
for n in nums[1:]:
low, high = 0, len(lis)
while low < high:
mid = (low + high) // 2
if lis[mid] < n:
low = mid + 1
else:
high = mid
if low == len(lis):
lis.append(n)
else:
lis[low] = n
return len(lis)


Comment :

LIS(Longest Increasing Subsequence)는 가장 전형적인 DP 문제이다. 위 접근법은 실제로 LIS를 만들어놓고 이진 탐색으로 삽입 위치를 찾는다. 삽입될 index에 기존 값이 있다면 n은 그 값보다 작거나 같기 때문에 갱신하고, 삽입될 index가 LIS 길이와 같다면, 즉 LIS의 최대값(마지막 원소)보다 n이 크다면 append 한다.