BOJ #11054(가장 긴 비트닉 하위 시퀀스)

by

어려움

골드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)