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

꼬인 전깃줄 문제와 같은 문제이다. 가장 긴 증가하는 부분수열 2,3을 풀었는데, 2에서는 숫자의 개수가 1000개까지, 3에서는 1,000,000개 까지 주어진다. 그래서 2를 풀 때는 여기에 포스팅 해놓은 LIS를 풀듯이 풀어도 되지만, 3을 풀 때는 여기에 포스팅 했던 꼬인 전깃줄 풀이처럼 풀어 시간복잡도를 줄여야 한다.

CODE

import sys
read = sys.stdin.readline

n = int(read())
num = list(map(int, read().split()))

dp = [num[0]]

def binsearch(x):
    l, r = 0, len(dp)
    while True:
        mid = (l+r)//2
        if dp[mid] == x:
            break
        elif mid == 0:
            if dp[mid] > x:
                dp[mid] = x
                break
            else:
                l += 1
        elif dp[mid] > x:
            if dp[mid-1] < x:
                dp[mid] = x
                break
            elif dp[mid-1] == x:
                break
            else:
                r = mid-1
        else:
            l = mid+1
    return


for x in num[1:]:
    if x > dp[-1]:
        dp.append(x)
    else:
        if len(dp) != 1:
            binsearch(x)
        else:
            dp = [x]
print(len(dp))


풀어야 할 문제

  • 스타트 택시
  • 미네랄
  • 회전 초밥
  • 아기 상어
  • 전깃줄 -2
  • 치즈