[LeetCode][Python3] 300. Longest Increasing Subsequence

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 한다.