[백준][이진탐색][LIS] 11054. 가장 긴 바이토닉 부분 수열

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

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

 

• 풀이
  • 최장증가부분수열을 구하는 LIS 함수를 만들어두고
  • 최장감소부분수열은 값에 -를 붙여서 LIS함수에 넘기면 같은 길이값을 반환함
  • i까지의 최장증가부분수열의 길이, i이후의 최장감소증가부분수열의 길이를 구해서 -1 (하나 값 중복되므로)

import bisect
def lis(arr):
    if not arr:return 0
    dp = [arr[0]]
    for i in range(len(arr)):
        if dp[-1]<arr[i]:
            dp.append(arr[i])
        else:
            dp[bisect.bisect_left(dp,arr[i])] = arr[i]
    return len(dp)
 
n = int(input())
num = list(map(int,input().split()))
answer = -1
for i in range(n):
    answer = max(answer,lis(num[:i+1])+lis([-x for x in num[i:]])-1)
print(answer)