BOJ 11054번 (가장 긴 바이토닉 부분 수열)

난이도

---

골드 IV

 

 

 

풀이

---

import sys

input=sys.stdin.readline

N=int(input())
arr=list(map(int,input().split()))
dp1=[1]*len(arr)
dp2=[1]*len(arr)
sub_len=[0]*len(arr)

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

arr.reverse()
for i in range(N):
    for j in range(i):
        if arr[i]>arr[j]:
            dp2[i] = max(dp2[i],dp2[j]+1)

dp2.reverse()
for i in range(len(arr)):
    sub_len[i]=dp1[i]+dp2[i]

print(max(sub_len)-1)

 

 

링크

---

https://www.acmicpc.net/problem/11054

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