목차

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

ps
링크acmicpc.net/…
출처BOJ
문제 번호14003
문제명가장 긴 증가하는 부분 수열 5
레벨플래티넘 5
분류

LIS

시간복잡도O(nlogn)
인풋사이즈n<=1,000,000
사용한 언어Python 3.11
제출기록157960KB / 952ms
최고기록904ms
해결날짜2024/02/02

풀이

코드

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

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

Tags: [LIS]
"""

from teflib import misc


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

    lis = misc.LongestMonotoneSubsequence(A)
    print(lis.length)
    print(*lis.subsequence)


if __name__ == '__main__':
    main()