[동적계획법] 가장 긴 바이토닉 부분 수열

가장 긴 증가하는 부분 수열의 응용버전이다.

이전 문제를 풀었다면 어렵지는 않은 문제일 것 같다.

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

from sys import stdin

N, A = int(stdin.readline()), list(map(int, stdin.readline().split(" ")))
T_L, T_R = [1] * N, [1] * N


def get_table_left(ind: int):
    m = 0
    for i in range(ind, -1, -1):
        if A[ind] > A[i] and m < T_L[i]:
            m = T_L[i]

    T_L[ind] = m + 1


def get_table_right(ind: int):
    m = 0
    for i in range(N - ind):
        if A[ind] > A[ind + i] and m < T_R[ind + i]:
            m = T_R[ind + i]

    T_R[ind] = m + 1


for i in range(N):
    get_table_left(i)
    get_table_right(N - i - 1)

print(max(T_R[i] + T_L[i] for i in range(N)) - 1)