最長バイトニック部分列とは？
最長バイトニック部分列（Longest Bitonic Subsequence）は、配列の中で順序を保ちながら、しばらく厳密に増加し、頂点を一つ打ってから厳密に減少する最長の部分列を求める問題です。一言で言えば「山型」です。
連続している必要はなく、元の順序さえ守ればOKです。上がるだけ・下がるだけでもバイトニックとして認められます。
なぜLISの変形なのか？
山型は頂点を境に二つの部分に分かれます。
- •頂点の左側：増加し続ける区間（上り）
- •頂点の右側：減少し続ける区間（下り）
ここで重要な観察があります。上りは正方向LIS（Longest Increasing Subsequence）、下りは配列を逆から見た逆方向LISと同じです。だからLISを二つ合成すればバイトニックになります。
動作原理
ステップ1. 正方向に inc[i] を計算 — iで終わる最長増加部分列の長さ。
ステップ2. 逆方向に dec[i] を計算 — iから始まる最長減少部分列の長さ（後ろからのLIS）。
ステップ3. 各iを頂点と仮定して inc[i] + dec[i] - 1 を計算します。頂点が両側で一度ずつ数えられるため1を引きます。
ステップ4. 全iの最大値が答えです。
例で追ってみる
高度配列 [1, 5, 2, 8, 4, 3] で見てみましょう。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| h | 1 | 5 | 2 | 8 | 4 | 3 |
| inc | 1 | 2 | 2 | 3 | 3 | 3 |
| dec | 1 | 2 | 1 | 3 | 2 | 1 |
| inc+dec-1 | 1 | 3 | 2 | 5 | 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²)（二重ループ2回） |
| 空間 | 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）です。
AlgoNoteで直接確認しましょう
正方向LISで上りを埋め、逆方向LISで下りを埋め、各頂点候補で二つの長さを合成する過程を、AlgoNoteでステップごとに見られます。高度配列を変えて頂点がどこに移動するか実験してみてください。