🥚質問する

🥚入力/出力

🍳コード#コード#

import sys
import bisect
input = sys.stdin.readline

n = int(input())
arr = [0] + list(map(int, input().split()))

# LIS = O(NlogN)
# dp[i] = 길이가 i인 증가하는 부분 수열의 마지막 숫자의 최소값

def LIS():
    dp = [0]
    for i in range(1, n+1):
        if arr[i] > dp[-1]:
            dp.append(arr[i])
        else:
            idx = bisect.bisect_left(dp, arr[i])  # 이분탐색으로 들어갈 자리 찾기
            dp[idx] = arr[i]
    return len(dp) - 1

ans = LIS()
print(ans)

🧂アイデア

DP, LIS