[백준]12738: 가장 긴 증가하는 부분 수열 3

이분탐색

가장 긴 증가하는 부분 수열 3

이 문제는 2 문제와 같지만 수열의 범위가 음수일때도 포함이 된다.
가장 긴 증가하는 부분 수열 2
이럴땐 시작 스택에 들어가는 수를 -1000000001로 지정해주면 된다.
나머지는 2랑 같음

import sys
from bisect import bisect_left
n = int(input())
lst = list(map(int, input().split()))
stack = [-1000000001]
for i in range(len(lst)):
	if stack[-1] < lst[i]:
		stack.append(lst[i])
	else:
		k = bisect_left(stack, lst[i])
		stack[k] = lst[i]
print(len(stack[1:]))