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

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

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

코드를 보면 알겠지만

• dp = 가장 긴 증가하는 부분수열
• dp2 = 가장 긴 감소하는 부분수열

을 각각 구하고, dp + dp2 -1(둘이 겹치는 부분, 꼭대기 부분) 이 가장 큰 값을 찾으면 된다.

 

import sys

n = int(sys.stdin.readline())

line = [int(i) for i in sys.stdin.readline().rstrip().split()]

dp = [0] * n
dp2 = [0]*n

if n ==1:
    print(1)
    sys.exit()

for i in range(n):
    dp[i] = 1
    for j in range(i):
        if line[i]>line[j] and dp[i] < dp[j]+1:
            dp[i] =  dp[j]+1
 

for i in range(n-1,-1,-1):
    dp2[i] = 1
    for j in range(n-1,i-1,-1):
        if line[i]>line[j] and dp2[i] < dp2[j]+1:
            dp2[i] =  dp2[j]+1

res = 0
for i in range(n):
    res = max(res, dp[i]+dp2[i]-1)

print(res)