728x90
분석
최대 부분 증가수열
분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는
karla.tistory.com
풀이
"""
왼쪽의 번호와 오른쪽의 번호, 같은 번호끼리 선으로 연결
왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열
오른쪽의 번호 정보가 위부터 아래 순서
서로 선이 겹치지 않고 최대 몇 개의 선 연결?
자연수 N(1<=N<=100)
1부터 N까지의 자연수 N개의 오른쪽 번호 정보
10
4 1 2 3 9 7 5 6 10 8
=> 6개 (123568)
"""
from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
d=[]
for i in arr:
k = bisect_left(d, i)
if len(d) == k:
d += [i]
else:
d[k] = i
print(len(d))
728x90