(백준) 12738 – 최장 증가 서브 시퀀스 3 (Python)

by

쉬운 목차

질문

12738: 최장 증가 서브 시퀀스 3(acmicpc.net)

#12738: 최장 증가 서브 시퀀스 3

'추천 관련글,

첫 번째 라인은 시퀀스 A의 크기 N을 제공합니다(1 ≤ N ≤ 1,000,000). 두 번째 행에는 시퀀스 A를 구성하는 Ai가 포함됩니다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

설명하다

12015 – Longest Incrementing Subsequence 2(Python) – GreenGroup 코드에서 한 가지 문제만 수정했습니다.

12015 – 최장 증가 하위 시퀀스 2(Python)

문제 12015: 최장 증가 서브 시퀀스 2(acmicpc.net) 질문 12015: 최장 증가 서브 시퀀스 2 첫 번째 줄은 시퀀스 A의 크기 N(1 ≤ N ≤ 1,000,000)을 제공합니다. 두 번째 줄에는 시퀀스 A를 구성하는 Ai가 제공됩니다.

그린그룹.co.kr

자세한 설명은 위의 포스팅을 참고해주세요.

from sys import stdin
from bisect import bisect_left
input = lambda : stdin.readline().strip()

N = int(input())
A = list(map(int, input().split()))
dp = (-10000000000)

for i in A :
    if dp(-1) < i :
        dp.append(i)
    else :
        dp(bisect_left(dp, i)) = i

print(len(dp) - 1)