[Beakjoon] #11054 - 가장 긴 바이토닉 부분 수열

정방향, 역방향 가장 긴 증가하는 수열을 구한뒤 각 dp의 값을 합쳐준다.
이때 -1을 하는 이유는 바이토닉 수열의 변곡점 부분의 dp 값이 2번 카운팅되기 때문이다.

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

A.insert(0, 0)
dpf = [1] * (N + 1) # 정방향
dpr = [1] * (N + 1) # 역방향
dps = [1] * (N + 1) # 합칠 때 

for i in range(1, N + 1): 
    for j in range(1, i):
        if A[j] < A[i]:
            dpf[i] = max(dpf[i], dpf[j]+1)

for i in range(N, 0, -1):
    for j in range(N, i, -1):
        if A[j] < A[i]:
            dpr[i] = max(dpr[i], dpr[j]+1)

for i in range(1, N + 1):
    dps[i] = dpf[i] + dpr[i] - 1

print(max(dps))