[백준] 12738 - 가장 긴 증가하는 부분 수열 3 (파이썬)

n = int(input())
array = list(map(int,input().split()))

def binary_search(start,end,target):
    if start>end:
        return start
       
    mid = (start+end)//2
    
    if total[mid] > target:
        return binary_search(start,mid-1,target)
    elif total[mid] == target:
        return mid
    else:
        return binary_search(mid+1,end,target)

total = [array[0]]
for i in range(1,len(array)):
    if total[-1] < array[i]:
        total.append(array[i])
    else:
        total[binary_search(0,len(total)-1,array[i])] = array[i]

print(len(total))

이분탐색 알고리즘 참고