[BOJ] 11054번 가장 긴 바이토닉 부분 수열

가운데 기준점을 옮겨가며 양방향에서의 LIS를 구하면 되는 문제이다.

N = int(input())
nums = list(map(int,input().split()))
dp = [1 for _ in range(N)] # 하나만 있는 수열이면 길이 1이므로

reverse_nums = nums[::-1]
reverse_dp = [1 for _ in range(N)]

# nums에서 index마다 LIS 최대길이 구하기
for i in range(1,N):
  for j in range(0,i):
    if nums[j] < nums[i]:
      dp[i] = max(dp[i],dp[j]+1)

# 뒤집은 nums에서 index마다 LIS 최대길이 구하기
for i in range(1,N):
  for j in range(0,i):
    if reverse_nums[j] < reverse_nums[i]:
      reverse_dp[i] = max(reverse_dp[i],reverse_dp[j]+1)      

#가운데는 값은 중복되므로 길이에서 마지막에 -1
print(max([x+y for x,y in zip(dp,reversed(reverse_dp))])-1)