백준 11054번 "가장 긴 바이토닉 부분수열"

문제

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

풀이

LIS의 응용문제.
11053번과 비슷하게 문제를 풀면된다.

11053번과 다른 것이 있다면 내림차순 수열을 구하고,
오름차순 수열과 내림차선 수열이 만나 최대 길이를 이루는
특정 위치를 구해야 한다.

입력받은 수열을 뒤집어 내림차순을 위한 배열을 만들고,
각 길이의 최대 값을 구해준 뒤,
특정 위치에서의 오름차순과 내림차순 배열의 최대치의 합을 구하면 된다.
(이때 특정 위치에서의 숫자가 한번 중복되므로 합에서 -1을 해주어야 한다.)

Python 코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr_rev = arr[::-1]

asc = [1]*n
desc = [1]*n

for i in range(1, n):
  for j in range(i):
    if arr[j] < arr[i]:
      asc[i] = max(asc[i], asc[j]+1)
    if arr_rev[j] < arr_rev[i]:
      desc[i] = max(desc[i], desc[j]+1)

answer = []
for i in range(n):
  answer.append(asc[i] + desc[n-i-1] - 1)

print(max(answer))