가장 긴 증가하는 부분 수열

• 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS)의 기본 문제. 링크에 설명한대로 이분탐색과 세그먼트 트리의 두가지 O(nlogn) 풀이법이 있다.
• 여기에서는 세그먼트 트리 방법으로 풀었다. A[i]의 범위와 N의 범위가 같아서 굳이 좌표압축도 하지 않았다.

"""Solution code for "BOJ 11053. 가장 긴 증가하는 부분 수열".

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

Tags: [LIS] [SegmentTree]
"""

from teflib import segmenttree


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

    size = max(A) + 1
    segtree = segmenttree.SegmentTree([0] * size, merge=max)
    for a_i in A:
        max_len = segtree.query(0, a_i)
        segtree.set(a_i, max_len + 1)

    max_len = segtree.query(0, size)
    print(max_len)


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree