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

• dp1은 가장 긴 증가하는 부분 수열의 길이임
• dp2는 가장 긴 감소하는 부분 수열의 길이인데, 현재 index에서 끝 index까지를 고려함
• • A를 역순으로 정렬한 수열에 대해 가장 긴 증가하는 부분 수열을 구하고, 이를 다시 역순으로 정렬하면 dp2를 구할 수 있음
• dp1과 dp2를 idx별로 더했을 때 최댓값을 갖는 경우가 가장 긴 바이토닉 부분 수열임
• dp1과 dp2를 그냥 더하면 Sk가 겹치므로 -1을 해줌

import sys

N = int(input())
A = list(map(int, sys.stdin.readline()[:-1].split(' ')))

dp1 = [0 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if A[i] > A[j] and dp1[i] < dp1[j]:
            dp1[i] = dp1[j]
    dp1[i] += 1

A.reverse()
dp2 = [0 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if A[i] > A[j] and dp2[i] < dp2[j]:
            dp2[i] = dp2[j]
    dp2[i] += 1
dp2.reverse()

tmp = []
for i in range(N):
    tmp.append(dp1[i] + dp2[i])

print(max(tmp) - 1)