백준_11054_가장 긴 바이토닉 부분수열(DP)

n = int(input())
a = list(map(int, input().split()))
a_r = list(reversed(a))

dp = [1] * n
dp_r = dp[:]

for i in range(1, n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)
        if a_r[j] < a_r[i]:
            dp_r[i] = max(dp_r[i], dp_r[j]+1)

result = [0]*n
for i in range(n):
    result[i] = dp[i] + dp_r[n-i-1] - 1
    
print(max(result))

LIS 알고리즘과 똑같이 진행하는데 입력 배열을 뒤집어서 한 번더 진행한다.

그 후 두 개의 LIS 결과를 더해 줌으로 써 증가했다 감소하는 수열의 최장 길이를 구할 수 있다.

백준 문제 11053 문제에서 한 번더 꼰 문제
https://www.acmicpc.net/problem/11053

11053 문제를 직전에 풀고 왔음에도 스스로 해결하지 못하고 인터넷을 찾아보고 해결할 수 있었다...