[알고리즘] 가장 긴 증가 부분 수열 LIS

• 임의의 수열에서 부분 수열을 만들 때, 증가하고 있는 부분 수열 중 가장 긴 수열

풀이 방법

1. Dynamic Programming

arr = [~]
dp = [1]*len(arr) # 현재 원소가 가질 수 있는 가장 긴 증가 부분 수열 길이

for i in range(len(arr)):
	for j in range(i):
    	if arr[i] > arr[j]:
        	# 이전 원소가 현재 원소보다 작을 때
            dp[i] = max(dp[i],dp[j]+1) # 가장 긴 길이를 저장, 이미 앞에서 더 긴게 나왔을 수도 있으니 현재 값과도 비교
print(max(dp))

2. Binary Search

import bisect
arr = [~]
dp = [arr[0]]

for i in range(len(arr)):
	if arr[i] > dp[-1]:
    	# 현재 위치가 이전 위치의 원소들보다 크면 dp에 추가한다.
    	dp.append(arr[i])
    else:
    	# 현재 위치가 이전 위치 원소보다 작거나 같으면,
        # bisect.bisect_left로 이전 원소 중 가장 큰 원소의 index값을 구한 후
        # dp의 index 원소를 arr[i]로 바꾼다.
    	idx = bisect.bisect_left(dp,arr[i])
        dp[idx] = arr[i]
print(len(dp))

• 아직 이해를 못했다..