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

문제

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

풀이

풀이는 11055번과 같다. i번째에서 가장 긴 바이토닉 부분 수열을 저장하면 된다. 그러기 위해서 수열 A를 뒤집은 re_A수열을 만들어서 반대로 똑같이 구한다. 그리고 난 뒤 다시 뒤집어서 더하고 1을 빼준다. 1을 빼주는 이유는 i번째 수가 중복되어서 카운트되었기 때문이다.

코드

from sys import stdin

input = stdin.readline

n = int(input())

array = list(map(int,input().split()))
re_array = array[::-1]

dp = [1 for i in range(n)]
re_dp = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if array[i] > array[j]:
            dp[i] = max(dp[j]+1,dp[i])
        if re_array[i] > re_array[j]:
            re_dp[i] = max(re_dp[j]+1,re_dp[i])

re_dp = re_dp[::-1]
#처음에 re_array로 뒤집어서 구했으니 다시 뒤집어준다.

for i in range(n):
    dp[i] = dp[i]+re_dp[i]-1
    #1을 빼는 이유는 i번째 수가 중복되어서 계산되었기 때문이다.

print(max(dp))

비슷한 문제

11055번 : 가장 큰 증가 부분 수열 / 풀이
11053번 : 가장 긴 증가하는 부분 수열 / 풀이
12015번 : 가장 긴 증가하는 부분 수열 2 / 풀이