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

출처::  www.acmicpc.net/problem/11054

분류:: dp

 

1. 문제 이해 및 해결과정

- dp[i] : i까지 수 중 가장 긴 바이토닉 수열의 길이 ex)         1  5  2  1  4  3  4  5  2  1  dp[0]     1  2  2  1  3  3  4  5  2  1  왼쪽부터 가장 긴 부분수열을 구한다  dp[1]     1  5  2  1  4  3  3  3  2  1  오른쪽부터 가장 긴 부분수열을 구한다.  dp[2]     1  6  4  3  5  6  6  7  7  3  가장 큰 값은 중복되므로 -1,  dp[0][i]+dp[1][i]-1

 

2. 풀이방법

  1. dp

#가장 긴 바이토닉 부분 수열
#https://www.acmicpc.net/problem/11054
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
dp=[[1]*n for _ in range(3)]
rever_a=a[::-1]
for i in range(n):
    for j in range(i):
        if a[i]>a[j]:
            dp[0][i]=max(dp[0][i],dp[0][j]+1)
        if rever_a[i]>rever_a[j]:
            dp[1][i]=max(dp[1][i],dp[1][j]+1)
dp[1]=dp[1][::-1]
dp[2][0]=1
for i in range(n):
    dp[2][i]=dp[0][i]+dp[1][i]-1
print(max(dp[2]))

  

3. 오답원인

 

4. 알게된 점