[백준] [DP] 가장 긴 바이토닉 부분 수열 11054 (파이썬)

스케치

코드

• 최장 증가 부분수열 (LIS)에 대한 이해가 필요하다.

# 가장 긴 바이토닉 부분 수열 
# LIS 문제
n = int(input())

arr =list(map(int,input().split()))

dpH = [1 for _ in range(n)] # 증가하는 부분
dpL = [1 for _ in range(n)] # 감소하는 부분

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
             dpH[i] = max(dpH[i], dpH[j]+1)

arr.reverse()
# 가장 긴수열을 용이하게 구하기 위해서 뒤집니다.

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dpL[i] = max(dpL[i], dpL[j] + 1)
# 뒤집어서 갚을 넣었기 때문에 dpL도 뒤집어 준다.
dpL.reverse()

maxSum = 0
for i in range(n):
    if maxSum < dpH[i] + dpL[i]:
        maxSum = dpH[i] + dpL[i]
print(maxSum - 1)