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

===== 풀이 =====
  * 기본적인 [[ps:가장 긴 증가하는 부분 수열]] 문제. 
  * [[ps:problems:boj:12015]]문제와는 n의 범위도 똑같고 a_i의 범위만 다르다. 세그먼트 트리 방법으로 풀때에는 좌표 압축의 필요 여부가 달라지지만, 이진탐색 방법으로 풀때에는 달라질 것이 전혀 없다. [[ps:problems:boj:12015]]문제와 동일한 코드로 통과했다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12738. 가장 긴 증가하는 부분 수열 3".

- Problem link: https://www.acmicpc.net/problem/12738
- Solution link: http://www.teferi.net/ps/problems/boj/12738

Tags: [LIS] [BinarySearch]
"""

import bisect


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    arr = []
    for a_i in A:
        pos = bisect.bisect_left(arr, a_i)
        if pos == len(arr):
            arr.append(a_i)
        else:
            arr[pos] = a_i

    print(len(arr))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}