백준 11054. 가장 긴 바이토닉 부분 수열

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

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

# 증가 DP
asc_dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if nums[j] < nums[i]:
            asc_dp[i] = max(asc_dp[i], asc_dp[j] + 1)

# 감소 DP
des_dp = [1] * n
for i in range(n - 2, -1, -1):
    for j in range(n - 1, i, -1):
        if nums[j] < nums[i]:
            des_dp[i] = max(des_dp[i], des_dp[j] + 1)

# 바이토닉 수열 길이 계산
ans = 0
for i in range(n):
    max_length = max(max_length, asc_dp[i] + des_dp[i] - 1)

print(ans)