[백준 / 11054] 가장 긴 바이토닉 부분 수열 - Python

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

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

 

<풀이>

2022.03.06 - [# Coding/# 백준] - [백준 / 11053] 가장 긴 증가하는 부분 수열 - Python

[백준 / 11053] 가장 긴 증가하는 부분 수열 - Python

2022.03.06 - [# Coding/# 백준] - [백준 / 11722] 가장 긴 감소하는 부분 수열 - Python

[백준 / 11722] 가장 긴 감소하는 부분 수열 - Python

 

위의 두 문제를 적절히 잘 조합하면 해당 문제의 답을 구할 수 있다.

 

바이토닉 수열은 증가하는 수열 + 감소하는 수열이다.

여기서 감소하는 수열을 구하는 것을 보면 dp[i]는 앞에서부터 i까지 구한 값이다. 하지만 위의 바이토닉 수열의 감소하는 수열은 뒤에서 부터 i까지 증가하는 수열을 구해야 한다. 즉, 바이토닉 수열은 증가하는 수열 + 역 증가하는 수열로 구해야 한다.

 

 

<전체 코드>

N = int(input())
arr = list(map(int, input().split()))

dp_orm = [1 for _ in range(N)]
dp_nrm = [1 for _ in range(N)]

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

max_arr = 0
for i in range(N):
    arrLen = dp_orm[i]+dp_nrm[i]-1
    if max_arr < arrLen:
        max_arr = arrLen
print(max_arr)