• 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS)문제. LIS의 길이뿐 아니라 LIS 시퀀스 한개를 함께 찾아야 한다.
• 가장 긴 증가하는 부분 수열 5의 쉬운 버전으로 O(n^2) 알고리즘으로도 통과되는 것을 의도한 문제이다.
• 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS) 에서 설명한대로 푸는 방법은 여러가지가 있고, DP(O(n^2)) < 세그먼트 트리(O(nlogn)) < 이진탐색(O(nlogn)) 순서대로 빠르다.
• 여기에서는 세그먼트 트리로 풀었다. a[i]의 범위가 N의 범위와 같아서 좌표 압축은 하지 않았다.
• 이진탐색 코드는 가장 긴 증가하는 부분 수열 5 참고.

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

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

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
    prev = []
    segtree = segmenttree.SegmentTree([(0, None)] * size, merge=max)
    for i, a in enumerate(A):
        max_len, pos = segtree.query(0, a)
        segtree.set(a, (max_len + 1, i))
        prev.append(pos)

    max_len, pos = segtree.query(0, size)
    answer = []
    while pos is not None:
        answer.append(A[pos])
        pos = prev[pos]

    print(max_len)
    print(*reversed(answer))


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree