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

문제

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)

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

풀이

LIS를 각각 0번 왼쪽 -> 오른쪽으로, 오른쪽->왼쪽으로 한번씩 하면 된다. 일반적인 LIS와 마찬가지로 이진탐색을 쓸 수 있고, 두 번 해주면 되겠다.

N = int(input())
A = [0] + list(map(int,input().split()))

left = [1]*1001
right = [1]*1001

for i in range(1,N+1):
    for j in range(1,i):
        if A[j] < A[i]:
            left[i] = max(left[i],left[j]+1)

for i in range(N,0,-1):
    for j in range(N,i,-1):
        if A[j] < A[i]:
            right[i] = max(right[i],right[j]+1)

print(max(map(lambda x : x[0]+x[1]-1,zip(left,right))))