[다이나믹 프로그래밍] 백준 11054번: 가장 긴 바이토닉 부분 수열 / 골드 3

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

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

well-known problem인 LIS를 조금 응용하면 풀 수 있는 문제!

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

dp_asc = [0 for _ in range(n)]
dp_desc = [0 for _ in range(n)]

for i in range(n):
    max_val = 0
    for j in range(i):
        if nums[j] < nums[i]:
            max_val = max(max_val, dp_asc[j])

    dp_asc[i] = max_val+1


nums.reverse()

for i in range(n):
    max_val = 0
    for j in range(i):
        if nums[j] < nums[i]:
            max_val = max(max_val, dp_desc[j])

    dp_desc[i] = max_val+1

answer = -1
for i in range(n):
    answer = max(answer, dp_asc[i] + dp_desc[n-1-i])
print(answer-1)