🔥

문제

북극곰 윌리는 주어진 수열에서 몇개를 뽑아 증가하는 수열을 만들려고 한다.


수열의 순서는 바꿀 수 없다.


수열 {10, 40, 20, 50, 30} 이 있을 경우, 증가하는 수열의 최대길이는 {10, 20, 30}으로 3이다.


윌리를 도와 증가하는 수열의 최대 길이를 구하자.

입력

첫째 줄에 수열의 길이 N이 주어진다. (1 ≤ N ≤ 1000)


둘째 줄에는 수열을 이루는 값 Xi들이 주어진다. (1 ≤ Xi ≤ 1000)

출력

첫째 줄에 증가하는 수열의 최대길이를 출력한다.

예제 1 입력

6
10 20 10 30 20 50

예제 1 출력

4

예제 2 입력

4
10 20 10 20

예제 2 출력

2

Source

import bisect

n = int(input())

LIS = [0 for _ in range(n)]
max_index = 0
k = []
k.append(0)
arr = list(map(int, input().split()))

for i in range(n):
    x = arr[i]

    LIS[i] = bisect.bisect_left(k, x)

    if(LIS[i] == len(k)):
        k.append(x)
	# 하단 이미지 참고
    k[LIS[i]] = x

    max_index = max(max_index, LIS[i])

print(max_index)

참고

참고