[BOJ] 11054. 가장 긴 바이토닉 부분 수열(python)

📌문제

💪아이디어

바이토닉 부분 수열은 기준이 되는 인덱스의 왼쪽은 증가하는 수열이고 오른쪽은 감소하는 수열이다. 그래서 증가하는 부분수열과 감소하는 부분수열을 모두 구해야한다.

1. 자기 자신은 무조건 포함되기 때문에 [1] * n로 초기화한다.
   

2. 증가하는 가장 긴 부분수열
   인덱스 i가 기준일때 0~i-1까지 자신보다 작은 값일때 arr[i] = max(arr[i],arr[작은 값 inx]+1)한다. 해당 inx의 값은 그 값보다 작은 값들의 누적수이기 때문에 +1해줘서 검사한다.
   

3. 감소하는 가장 긴 부분수열
   2번 과정과 비슷한데 n-1~i+1까지 검사한다.
   

4. LIS + LDS한 최댓값의 인덱스 구하기
   r최댓값에 해당하는 인덱스가 기준이 될 경우 가장 긴 바이토닉 부분 수열이 된다

🥂코드

import sys; input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
iDp, dDp = [1] * n, [1] * n

for i in range(n):
    for j in range(i):
        if A[i] > A[j]:
            iDp[i] = max(iDp[i],iDp[j]+1)

for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if A[i] > A[j]:
            dDp[i] = max(dDp[i],dDp[j]+1)

answerDp=[0]*n
for i in range(n):
    answerDp[i] = iDp[i] + dDp[i]

print(max(answerDp)-1)