백준11504: 가장 긴 바이토닉 부분 수열 (Python/파이썬)

import sys
input = sys.stdin.readline

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

asc_dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if A[i] > A[j]:
            asc_dp[i] = max(asc_dp[i], asc_dp[j]+1)

desc_dp = [1] * n
for i in range(n-1, -1, -1):
    for j in range(n-1, i, -1):
        if A[i] > A[j]:
            desc_dp[i] = max(desc_dp[i], desc_dp[j]+1)

res = 1
for i in range(n):
    temp = asc_dp[i] + desc_dp[i] - 1
    res = max(temp, res)

print(res)

각 인덱스 별로 dp를 통해 0~i까지의 최장 증가 부분수열과 i~N까지의 최장 감소 부분수열을 구한 뒤 합친 값의 최댓값을 구한다.