사용자 도구

사이트 도구


ps:problems:boj:11053

가장 긴 증가하는 부분 수열

ps
링크acmicpc.net/…
출처BOJ
문제 번호11503
문제명가장 긴 증가하는 부분 수열
레벨실버 2
분류

LIS

시간복잡도O(nlogm)
인풋사이즈n<=1000, m<=1000
사용한 언어Python
제출기록33952KB / 152ms
최고기록56ms
해결날짜2021/06/15

풀이

코드

"""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()

토론

댓글을 입력하세요:
R K X B E
 
ps/problems/boj/11053.txt · 마지막으로 수정됨: 2021/12/23 12:06 저자 teferi