[BinarySearch w/LIS] 반도체설계

LIS 설명 블로그

seungkwan.tistory.com/8

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

# 2352, 반도체 설계
import sys
input = sys.stdin.readline

def lower_bound(s, e, v):
    while s < e:
        m = (s+e) // 2
        if lst1[m] < v:
            s = m + 1
        else:
            e = m
    return e

n = int(input())
port = list(map(int, input().split()))
lst1 = []

for i in range(n):
    if i == 0:
        lst1.append(port[i])
    else:
        if port[i] > lst1[-1]:
            lst1.append(port[i])
        else:
            tmp = lower_bound(0, len(lst1), port[i])
            lst1[tmp] = port[i]

print(len(lst1))

코드 출처: li-fo.tistory.com/56

파이썬 | 백준 | 2352 | 반도체 설계