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

📒문제

🎈풀이

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

dp_inc = [1 for _ in range(N)]
for i in range(1, N):
  for j in range(i):
    if(arr[i] > arr[j]): dp_inc[i] = max(dp_inc[i], dp_inc[j]+1)

dp_dec = [1 for _ in range(N)]
for i in range(N-1, -1, -1):
  for j in range(i):
    if arr[i] < arr[j]: dp_dec[j] = max(dp_dec[i]+1, dp_dec[j])


result = []
for i in range(N):
  result.append(dp_inc[i]+dp_dec[i]-1)

print(max(result))

dp_inc는 순서대로 커지는 최대 배열 길이를 담은 배열이고,
dp_dec는 순서대로 작아지는 최대 배열 길이를 담은 배열이다.

이때 result[i] 는 dp_inc[i] + dp_dec[i]-1을 담는데,

dp_inc[i]는 s1<s2<....s(i-1)<s(i)를 만족하는 배열의 최대의 길이이며,
dp_dec[i]는 s(i)>s(i+1)>.....s(N-1)>s(N)을 만족하는 배열의 최대의 길이다.

따라서 이 둘을 더한다면 s1<s2<....s(i-1)<s(i)>s(i+1)>.....s(N-1)>s(N)
을 만족하는 배열의 최대 길이를 구할수 있다. 이때 -1을 해주는 건 s(i)가 dp_inc와 dp_dec의 길이의 전부 포함되어 있어 중복을 제거해주는 것이다.

나름 깔끔하게 풀어 기분 좋은 문제!