LIS 가장 긴 증가하는 부분 수열

1. dp를 이용한 풀이

N = int(input())
arr = list(map(int, input().split()))
dp = [1] * N

for i in range(N):
    for j in range(i):
        if arr[j] <= arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

 

 

 

2. 이분 탐색을 이용한 풀이 (더 빠르다)

N = int(input())
A = list(map(int, input().split()))
LIS = [A[0]]

def find_index(x):
    lo = 0
    hi = len(LIS) - 1

    while lo <= hi:
        mi = (lo + hi) // 2
        if LIS[mi] < x:
            lo = mi + 1
        else:
            hi = mi - 1

    return lo

for item in A:
    if LIS[-1] < item:
        LIS.append(item)
    else:
        LIS[find_index(item)] = item

print(len(LIS))