가장 긴 바이토닉 부분 수열 문제(Longest Bitonic Subsequence Problem)는 주어진 배열에서 우선 값이 증가했다가 그 후 감소하는 원소들의 집합 중 가장 긴 부분 수열을 찾는 문제입니다.
배열이 주어졌을 때, 가장 긴 바이토닉 부분 수열을 찾으시오.
부분 수열은 주어진 배열 원소들의 순서를 유지하는 원소들의 집합입니다.
연속된 원소들이 선택될 필요는 없습니다.
단, 증가만 하거나 감소만 하는 부분 수열도 답이 될 수 있습니다.
-
Input: [4, 2, 5, 9, 7, 6, 10, 3, 1]
-
Output: [4, 5, 9, 7, 6, 3, 1]
-
Input: [1, 2, 3, 4, 5]
-
Output: [1, 2, 3, 4, 5]
-
Input: [5, 4, 3, 2, 1]
-
Output: [5, 4, 3, 2, 1]