<aside> ✅ 최적의 코드 (이진 탐색)

</aside>

# 10: 15
import sys

user_input = sys.stdin.readline;
user_print = sys.stdout.write;

n = int(user_input());
numArr = list(map(int, input().split()));

def binary_search(arr, target):
    start, end = 0, len(arr) - 1;
    while start <= end:
        mid = (start + end) // 2;
        if arr[mid] < target:
            start = mid + 1;
        else:
            end = mid - 1;
    return start

# 맨 처음 인덱스
lis = [numArr[0]]

for i in range(1, len(numArr)):
    if numArr[i] > lis[-1]:
        lis.append(numArr[i]);
    else:
        index = binary_search(lis, numArr[i]);
        lis[index] = numArr[i];

user_print(str(lis));

<aside> ✅ DP

</aside>

import sys

user_input = sys.stdin.readline;
user_print = sys.stdout.write;

n = int(user_input());
numArr = list(map(int, input().split()));
# 감소하는 부분 수열 길이 담은 배열
countArr = [1 for _ in range(n)];

for i in range(1, n):
    for j in range(i):
        # 다음 인덱스 숫자가 클 경우 -> 증가가 일어남
        if numArr[i] > numArr[j]:
            # 현재 카운트 배열 요소, 이전 카운트 배열 요소에 + 1을 한 값
            countArr[i] = max(countArr[i], countArr[j] + 1);

user_print(str(max(countArr)));