[DP] 11054번 - 가장 긴 바이토닉 부분 수열(55일차)

#python 입출력 시간 단축
import sys
input = sys.stdin.readline

#수열의 길이, 수열 입력
N = int(input())
array = list(map(int, input().split()))

#좌->우로 해당 지점까지의 최장 부분 증가 수열을 저장하는 dp
dp_left = [0 for _ in range(N)]
#우->좌로 해당 지점까지의 최장 부분 증가 수열을 저장하는 dp
dp_right = [0 for _ in range(N)]

#수열의 길이만큼 반복
for i in range(N):
    #탐색 지점 이전 리스트 요소의 개수만큼 반복
    #각 탐색 지점에 대해 해당 지점 이전까지 저장된 최장 부분 증가 수열의 길이를 복사
    for j in range(i):
        #좌->우로 증가하는 부분 수열
        if(array[j] < array[i] and dp_left[j] > dp_left[i]):
            dp_left[i] = dp_left[j]
        #우->좌로 증가하는 부분 수열
        if(array[-1-j] < array[-1-i] and dp_right[-1-j] > dp_right[-1-i]):
            dp_right[-1-i] = dp_right[-1-j]

    #각 지점의 길이가 그 자체로 1이므로 길이에 1을 더함
    dp_left[i] += 1
    dp_right[-1-i] += 1

#좌->우 증가 수열과 우->좌 증가 수열 dp의 값을 서로 더해 각 지점을 기준으로 하는 최장 바이토닉 수열을 구함
dp_result = [x+y for x,y in zip(dp_left,dp_right)]

#최대값 출력
print(max(dp_result)-1)

#인사이트
#양방향 이진 탐색과 dp 알고리즘을 병용한 출제 유형
#NxN 사이즈 list로 풀이가 가능하지만, 시공간 복잡도 조건 상의 문제로 2개의 1차원 dp를 사용해 풀이하는 것이 합리적인 문제
#바이토닉 중심 지점을 기반으로 양방향 탐색을 하는 것보다 2개의 역방향 dp 탐색을 합치는 것이 효율적인 접근방식