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

문제

접근 방법

1. 증가했다가 감소하는 sequence, 증가만 하는 sequence, 감소만 하는 sequence의 길이를 모두 비교해야 하는 문제여서 순서대로의 LIS(dp)을 구하고 반대 순서(reversed_dp)로도 LIS를 구했다. (이 반대 순서의 LIS는 감소하는 longest sequence 길이를 구하는 것이다.)

2. 각 index까지 증가하는 부분의 길이와 감소하는 부분의 길이를 구해서 두 길이의 합의 최대값으로 바이토닉 부분 수열의 최대 길이를 구하고자 했다. 이 합의 최대값을 ans 배열 안에 넣었다.

3. 증가만 하는 sequence의 최대 길이와 감소만 하는 sequence의 최대 길이 또한 ans 배열 안에 넣어서 최종 최대값을 구했다.

정답 코드

import sys
input = sys.stdin.readline

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



"""
원래 순서대로 LIS를 적용하고 반대 순서로 LIS를 적용한 후, 양쪽 방향에서의 LIS의 합, 증가만 하는 LIS, 감소만 하는 LIS 값 중 최대값을 찾으면 된다.
"""

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

reversed_arr = list(reversed(arr))
reversed_dp = [1]*n
for i in range(n):
    for j in range(i):
        if reversed_arr[j] < reversed_arr[i]:
            reversed_dp[i] = max(reversed_dp[i], reversed_dp[j]+1)

# print(dp)
# print(reversed_dp)

ans = []
a1 = 0
for i in range(n-1):
    for j in range(n-i-2, -1, -1):
        if reversed_arr[j] != arr[i]:
            a1 = max(a1, dp[i] + reversed_dp[j])

ans.append(a1)
ans.append(max(dp))
ans.append(max(reversed_dp))
print(max(ans))