[백준] 11054 - 가장 긴 바이토닉 부분 수열 [Python(파이썬)]

문제

www.acmicpc.net/problem/11054

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

풀이

가장 큰 증가 부분 수열 문제의 응용 문제다.

 

이중 for문을 두 번 구성하여 dp[n][0]엔 왼쪽부터 증가하는 가장 긴 부분 수열의 길이를 기록하고, dp[n][1]엔 오른쪽부터 증가하는 가장 긴 부분 수열의 기록을 기록한다. 

 

중복으로 겹쳐지는 부분이 있기 때문에 해를 구할 땐 1을 빼줘야 한다.

 

코드

import sys

n = int(sys.stdin.readline().strip())
a = [int(x) for x in sys.stdin.readline().split()]
dp = [[1 for _ in range(2)] for _ in range(n)]

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i][0] = max(dp[i][0], dp[j][0]+1)

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

dp = list(map(lambda x: x[0]+x[1], dp))

print(max(dp)-1)