문제출처 : https://www.acmicpc.net/problem/12015

풀이과정

1. 반복문을 돌며 stack의 마지막 값보다 클 경우 append
2. 작을 경우 이진탐색을 하여 stack을 완성한다.(stack 내부는 실제 부분수열과는 다를 수 있다.)

import sys

def find(target):
    s,e = 1, len(stack)-1
    while s < e:
        m = (s+e)//2
        if stack[m] < target:
            s = m + 1
        elif stack[m] > target:
            e = m
        else:
            s = e = m
    return e
l = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
stack = [0]

for a in arr:
    if stack[-1] < a:
        stack.append(a)
    else:
        stack[find(a)] = a

print(len(stack)-1)

필자는 LIS알고리즘을 Nlogn으로 구현하는데 하루 이상이 걸렸다 ㅠ..