최장 바이토닉 부분 수열이란?

최장 바이토닉 부분 수열(Longest Bitonic Subsequence)은 배열에서 순서를 유지하면서 한동안 엄격히 증가하다가, 정점을 찍은 뒤 엄격히 감소하는 가장 긴 부분 수열을 찾는 문제입니다. 한마디로 "산 모양"입니다.

연속일 필요는 없고 원래 순서만 지키면 됩니다. 올라가기만 하거나 내려가기만 해도 바이토닉으로 인정합니다.

왜 LIS의 변형인가?

산 모양은 정점을 기준으로 두 부분으로 나뉩니다.

여기서 핵심 관찰이 나옵니다. 오르막은 정방향 LIS(Longest Increasing Subsequence), 내리막은 배열을 뒤집어서 본 역방향 LIS와 같습니다. 그래서 LIS 두 개를 합치면 바이토닉이 됩니다.

1단계. 정방향으로 inc[i] 계산 — i에서 끝나는 최장 증가 부분 수열의 길이.

2단계. 역방향으로 dec[i] 계산 — i에서 시작하는 최장 감소 부분 수열의 길이(뒤에서부터 LIS).

3단계. 각 i를 정점이라 가정하고 inc[i] + dec[i] - 1을 계산합니다. 정점이 양쪽에서 한 번씩 세어지므로 1을 뺍니다.

고도 배열 [1, 5, 2, 8, 4, 3]로 보겠습니다.

정점 i=3(고도 8)에서 inc=3, dec=3 → 3+3-1=5가 최댓값입니다. 실제 수열은 [1, 2, 8, 4, 3] — 1<2<8로 올라갔다가 8>4>3으로 내려옵니다.

복잡도
시간	O(n²) (이중 반복 두 번)
공간	O(n) (inc, dec 배열)

LIS를 O(n log n) 이진 탐색으로 구하면 전체도 O(n log n)으로 줄일 수 있지만, 정점 분해 아이디어를 이해하는 데는 O(n²) 버전이 더 명확합니다.

•정점 중복 계산: inc[i] + dec[i]만 더하면 정점을 두 번 세게 됩니다. 반드시 -1을 해야 합니다.
•등호 처리: "엄격히 증가/감소"이므로 비교는 <로, <=를 쓰면 같은 값이 끼어 산 모양이 깨집니다.
•역방향 방향 혼동: dec는 i에서 "오른쪽으로 내려가는" 길이입니다. 뒤에서부터 채우되, 조건은 h[j] < h[i] (j>i)로 작은 값을 찾습니다.

정방향 LIS로 오르막을 채우고, 역방향 LIS로 내리막을 채운 뒤, 정점마다 두 길이를 합치는 과정을 알고노트에서 단계별로 볼 수 있습니다. 고도 배열을 바꿔가며 정점이 어디로 이동하는지 실험해보세요.