[백준 11054번] 가장 긴 바이토닉 부분 수열 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())

seq = deque(map(int,input().split()))
seq.appendleft(0)
seq.append(0)

DP1 = [0]*(N+1)
DP2 = [0]*(N+1)


for i in range(1,N+1):
  for j in range(i):
    if seq[i] > seq[j]:
      DP1[i] = max(DP1[i],DP1[j]+1)

for i in range(1,N+1):
  for j in range(i):
    if seq[-1-i] > seq[-1-j]:
      DP2[-1-i] = max(DP2[-1-i],DP2[-1-j]+1)

DP3 = [0]*N
for i in range(N):
  DP3[i] = DP1[i+1]+DP2[i]

print(max(DP3)-1)

처음에는 어떻게 풀어야 할지, 가장 긴 증가하는 부분수열을 구한다음 거기서부터 가장 긴 감소하는 부분수열을 찾는건가? 하고 고민했다. 근데 생각해보니까 그냥 처음부터 가장 긴 증가하는 부분수열 DP구하고, 뒤에서부터도 DP 구한다음 합치면 되는거였다...

 

 

오늘의 교훈) 괜히 복잡하게 생각하지 말자. 골드에서 어마어마하게 복잡한 문제는 없다.