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

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

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

문제 한줄 이해

- 주어진 수열에서 가장 긴 바이토닉 수열 찾기

생각난 풀이

1번째 방법: 이전에 풀이한 가장 긴 증가하는 부분 수열문제가 떠올랐고 이를 활용해보도록 했다.

바이토닉 수열은

계속 증가하거나

계속 감소하거나

계속 증가하다가 작아지는 순간에 계속 작아지는 수열이다. 그래서 디피를 활용해 0인덱스 에서부터 계속 증가하는 가장 긴 부분수열을 찾고 거꾸로 맨 뒤 인덱스에서부터 계속 증가하는 가장 긴 부분수열을 찾았다.(뒤에서 부터 가장 긴 부분 수열이라는건 앞에서보면 감소하는 가장 긴 부분 수열이다!)

그래서 앞 기준[1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
           뒤 기준[1, 5, 2, 1, 4, 3, 3, 3, 2, 1] 이 두개의 디피리스트를 합친다면 결국 증가하다가 감소하는 수열의 길이를 구할수 있다.

따라서 두리스트를 더해 -1을 하면 최종 답을 구할 수 있다.  -> -1을 하는 이유 한 지점의 인덱스가 겹치기 때문

import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))

bdp = [1] *(n)
sdp =[1] *(n)
for i in range(n):
    for j in range(i,n):
        if a[i] < a[j]: # 커지는
            bdp[j] = max(bdp[i]+1,bdp[j])
        if a[n-1-i] < a[n-1-j]: # 작아지는
            sdp[n-j-1] = max(sdp[n-i-1]+1,sdp[n-j-1])
result = 0
for i in range(n):
    if result < bdp[i]+sdp[i] -1:
        result = bdp[i]+sdp[i] -1
print(result)