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

풀이

바이토닉 수열은 ‘증가하는 부분 + 기준점 + 감소하는 부분’으로 나뉠 수 있다.
그렇다면 dp1 배열에는 i까지 증가하는 부분 수열의 길이를 담고, dp2 배열에는 뒤에서부터 i까지 감소하는 부분 수열의 길이를 담는다.
이 두 수열의 원소를 더하면 증가하는 부분 수열과 감소하는 부분 수열이 더해진 바이토닉 수열의 길이를 알 수 있다.
다만 기준점이 각각 포함되어 두 번 더해졌으므로 -1을 한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
dp1 = [0 for i in range(n)] # 증가하는 부분 수열
dp2 = [0 for i in range(n)] # 감소하는 부분 수열
ans = [0 for i in range(n)] # dp1 + dp2를 저장할 배열

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp1[i] = max(dp1[j], dp1[i])
    dp1[i] += 1

for i in range(n-1, -1, -1):
    for j in range(n-1, i, -1):
        if arr[i] > arr[j]:
            dp2[i] = max(dp2[j], dp2[i])
    dp2[i] += 1

for i in range(n):
    ans[i] = dp1[i] + dp2[i] -1

print(max(ans))