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

1. 문제 링크

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

2. 코드

import sys

input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
incresed_dp = [0] * n
decresed_dp = [0] * n

# 좌측에서부터 증가하는 부분 수열 탐색
for i in range(n):
    flag = 0
    for j in range(i - 1, -1, -1):
        if a[j] < a[i]:
            incresed_dp[i] = incresed_dp[j] + 1
            flag = max(flag, incresed_dp[j] + 1)
    if flag:
        incresed_dp[i] = flag
    else:
        incresed_dp[i] = 1

# 우측에서부터 증가하는 부분 수열 탐색
for i in range(n - 1, -1, -1):
    flag = 0
    for j in range(i + 1, n):
        if a[j] < a[i]:
            flag = max(flag, decresed_dp[j] + 1)
    if flag:
        decresed_dp[i] = flag
    else:
        decresed_dp[i] = 1


ans = list(map(sum, list(zip(incresed_dp, decresed_dp))))
print(max(ans) - 1)