BOJ - 11054 - 가장 긴 바이토닉 부분 수열

Updated:

import sys

def solution():
    N = int(input())
    number = list(map(int, sys.stdin.readline().split()))
    leftDp = [1] * N
    rightDp = [1] * N

    for i in range(N):
        for j in range(i):
            if number[i] > number[j]:
                leftDp[i] = max(leftDp[i], leftDp[j] + 1)
    number.reverse()

    for i in range(N):
        for j in range(i):
            if number[i] > number[j]:
                rightDp[i] = max(rightDp[i], rightDp[j] + 1)
    rightDp.reverse()

    ret = [0] * N
    for i in range(N):
        ret[i] = leftDp[i] + rightDp[i]
    print(max(ret)-1)

solution()

https://www.acmicpc.net/problem/11054

Categories:

Updated:

Leave a comment