1. 문제

출처: 백준 11054번 가장 긴 바이토닉 부분 수열

2. 풀이

이 문제는 수가 커지다가 작아지는 형태의 부분 수열을 구하는 것을 다루고 있다.

백준 11053번 가장 긴 증가하는 부분 수열 문제 풀이에서 점점 수가 커지는 부분 수열의 길이를 구하는 방법을 다뤘다. 해당 풀이를 바탕으로, 작아지는 부분 수열은 리스트를 reverse하여 구할 수 있다.

위의 설명과 같이 수열의 각 위치까지 바이토닉 부분 수열의 길이를 구하고, 최댓값을 출력하면 된다.

3. 소스코드

n = int(input())
numbers = list(map(int,input().split()))

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

numbers.reverse()
dp_reverse = [1]*n
for i in range(n):
    for j in range(i):
        if numbers[i] > numbers[j]:
            dp_reverse[i] = max(dp_reverse[i],dp_reverse[j]+1)

dp_total = []
for i in range(n):
    dp_total.append(dp_reverse[i]+dp[n-i-1]-1)
print(max(dp_total))

4. 그 외