🦊 가장 긴 바이토닉 부분 수열

1. 문제 링크

11054번: 가장 긴 바이토닉 부분 수열

2. 코드

Python3 31120KB 284ms

N  = int(input())

A = list(map(int, input().split()))

dp_up = [1] * N
dp_down = [1] * N

# 오름차순 DP
for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            dp_up[i] = max(dp_up[j] + 1, dp_up[i])

# 내림차순 DP
for i in range(N - 1, -1, -1):
    for j in range(N - 1, i, -1):
        if A[j] < A[i]:
            dp_down[i] = max(dp_down[j] + 1, dp_down[i])
result = 0
for i in range(N):
    result = max(dp_up[i] + dp_down[i] - 1, result);
print(result)

3. 해설

시작부터, 마지막부터 시작하는 오름차순 DP를 두개 만듬

두 DP의 MAX 값이 증가했다가 감소하는 부분 수열이 된다