[백준] 12738 – 가장 긴

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 – 가장 긴 증분 하위 시퀀스 2(Python) – GreenGroup 코드에서 한 가지 문제만 수정했습니다.

12015 – 최장 상승 하위 시퀀스 2(Python)

예제 12015: 최장 증가 서브 시퀀스 2(acmicpc.net) 예제 12015: 최장 증가 서브 시퀀스 2 첫 번째 라인은 시퀀스 A의 크기 N(1 ≤ N ≤ 1,000,000)을 제공합니다.

두 번째 줄에는 시퀀스 A를 형성하는 Ai가 제공됩니다.

greengroup.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)