[백준][Python] 11054 가장 긴 바이토닉 부분수열.

LIS 시리즈 문제중 하나이다. 역순으로도 구해서 각 지점 카운트합이 가장 높아지는 부분이 꺽이는 부분.

 

N = int(input())
A = [0] + list(map(int, input().split()))
LDS = [1]*(N+1)
LIS = [1]*(N+1)
Bi = []

# 바이토닉 수열의 핵심은 앞에서 LIS하고 역순 LIS dp를 각각 만들어
# 두 dp 인자의 합 = 올라갔다 내려오는 cnt를 만드는 것.
# 싸피 CT문제 예제로 나오는 문제라 아이디어는 매우 쉬웠다.
for i in range(1,N+1):
    for j in range(1,i):
        if A[i]>A[j] and LIS[i]<=LIS[j]:
            LIS[i] = LIS[j] + 1
        if A[-i]>A[-j] and LDS[-i]<=LDS[-j]:
            LDS[-i] = LDS[-j] + 1
for i in range(1,N+1):
    Bi.append(LIS[i]+LDS[i]-1)
print(max(Bi))