알고리즘/백준
[백준] 12015번 가장 긴 증가하는 부분 수열 2 (파이썬)
알감자
2022. 1. 2. 01:42
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
코드
import sys
def find(i):
low, high = 1, len(stack)-1
while low < high:
mid = (low+high)//2
if stack[mid] < i:
low = mid +1
elif stack[mid] > i:
high = mid
else:
low = high = mid
return high
if __name__ == '__main__':
n = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
stack = [0]
for i in li:
if stack[-1] < i:
stack.append(i)
else:
stack[find(i)] = i
print(len(stack)-1)