問題と適用シナリオ
整数配列 nums が与えられたとき、最長の狭義単調増加部分列（Strictly Increasing Subsequence）を1つ返してください。部分列は入力の相対的な順序を保ちますが、連続している必要はありません。「狭義単調増加」とは、次の各値がより大きくなければならないことを意味するため、等しい値によって長さを伸ばすことはできません。最適な解が複数存在する場合は、そのいずれかを返してください。入力が空の場合は空の配列を返してください。
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: [2, 3, 7, 18]
Increasing indices: 2 < 4 < 5 < 7
Increasing values: 2 < 3 < 7 < 18
Length: 40 ≤ n ≤ 100,000、符号付き32ビット整数値、および変更してはならない入力配列を前提とします。この規模では、部分列の全列挙や、最終的な解法としての2乗時間の動的計画法（DP）は除外されます。LeetCodeの問題では狭義単調増加部分列の長さを求めており、明確なフォローアップとして O(n log n) の目標が提示されています。2026年4月付けの公開面接対策記事でも、2乗DPと二分探索による最適化の両方が解説されています。本バージョンでは、さらに実際の一連の部分列も返します。これらの情報源は問題とその現在の対策価値を示すものであり、面接での出題頻度や特定企業への帰属を保証するものではありません。
面接官が評価するポイント
第1の評価ポイントは、正確な状態定義です。2乗DPの解法では、dp[i] を「必ず nums[i] で終わる最善の長さ」として定義する必要があります。単に「最初の i 個の値に対する答え」とするだけでは、現在の要素を追加できるかどうかを判断するために必要な末尾の値が捨てられてしまいます。
第2の評価ポイントは、ボトルネックから最適化を導出できることです。各 i に対して過去のすべての j を走査すると、O(n²) のコストがかかります。より優れた回答では状態を変更します。到達可能な各長さに対して、最小の末尾値のみを保持します。末尾の値が小さいほど、その後の拡張が容易になります（あるいは同等です）。これらの最小末尾値は狭義の単調増加になるため、更新位置を二分探索で見つけることができます。
第3の評価ポイントは、重複値の正確な処理です。狭義単調増加列では、末尾値が現在の値以上となる最初の位置（lower-bound セマンティクス）が必要です。等しい値は同じ位置を置き換えるだけであり、長さを拡張しません。非減少列（広義単調増加）のバリアントでのみ、その値より厳密に大きい最初の位置を使用します。
第4の評価ポイントは、tails 自体が答えではないと理解していることです。[3, 5, 6, 2] の処理後、末尾の値は [2, 5, 6] になります。これらは値としては増加していますが、元の入力インデックスは 3, 1, 2 となっており、部分列を構成していません。実際の経路を復元して返すには、各末尾の長さに対する現在の入力インデックスと、各要素の直前（predecessor）インデックスも保持する必要があります。
最後の評価ポイントは、証明と検証です。候補者は、最小末尾値の不変条件、値の置き換えによって最適解の長さが失われない理由、直前リンクが有効なパスを形成する理由、そして単一の例に頼るのではなく、ランダムな小さな入力を用いて O(n²) のオラクルと比較検証する方法を説明できる必要があります。
回答前に確認すべき質問
- 狭義単調増加（strictly increasing）か、非減少（non-decreasing）か？ この問題は厳密な単調増加であるため、重複値によって答えを拡張することはできません。等しい値が許容される場合、二分探索の境界条件が変わります。
- 長さを返すのか、それとも実際の列を返すのか？ この問題では列を返すため、
previousと末尾のインデックスが必要です。長さのみを求める解法であれば、補助空間をO(L)（Lは解の長さ）まで削減できます。 - 最適な解が複数ある場合のタイブレークはどのように処理すべきか？ いずれの解を返しても構いません。辞書順最小、インデックス最小、または安定選択の要件がある場合は、追加のルールと証明が必要になります。
- 入力サイズはどのくらいか？ 10万要素の場合は
O(n log n)を使用します。数百要素程度であれば、2乗DPの方が実装・説明が容易で、組み合わせ数のカウントなどにも拡張しやすいです。 - 入力が空になることはあるか？ はい、その場合は
[]を返します。これにより、復元処理で最終的な末尾インデックスを読み取ってよいかが決まります。 - 入力を変更してもよいか？ いいえ。ソートすると元のインデックス順が失われ、別の問題になってしまいます。
- 整数の算術オーバーフローは発生するか？ アルゴリズムは値の比較とコピーのみを行い、算術演算は行わないため、アルゴリズム起因で符号付き32ビット入力がオーバーフローすることはありません。
30秒の回答フレームワーク
「到達可能な各長さについて、最小の末尾値を保持します。これらの末尾値はソートされた状態になるため、各値について二分探索で『その値以上となる最初の末尾値』を見つけ、その位置を置き換えるか末尾に追加します。この lower bound により、重複値によって狭義増加列が誤って拡張されるのを防ぎます。末尾値の配列は入力インデックスの前後関係が混ざる可能性があるため、各末尾値の元のインデックスと要素ごとの直前インデックスも記録し、後方から経路を復元します。要素あたり1回の二分探索を行うことで、計算量は O(n log n) 時間、O(n) 空間となります。空配列、重複値、降順配列、およびランダムな小規模配列を用いて、2乗DPオラクルと比較テストします。」
ステップバイステップの詳細解法
まずは証明が最も容易なベースラインから始めます。dp[i] を、必ず nums[i] で終わる最長狭義単調増加部分列の長さとします。長さが2以上の任意の解は、nums[j] < nums[i] を満たすある j < i に直前の要素を持ちます：
dp[i] = 1 + max(dp[j]) over j < i and nums[j] < nums[i]
If no such j exists, dp[i] = 1
Final length = max(dp[i])この定義は漸化式の正当性も証明しています。条件を満たすすべての直前要素は nums[i] によって拡張可能であり、nums[i] で終わる任意の最適列はそれらの直前要素のいずれかから遷移しなければなりません。問題は、各 i がそれ以前のすべての位置を走査するため、全体で O(n²) の時間がかかる点です。
最適化のために、次のプレフィックス不変条件を維持します：最初の i 個の要素を処理した後、tails[k] は長さ k + 1 のすべての狭義単調増加部分列の中で最小の末尾値となります。現在の値 x に対し、tails[k] ≥ x を満たす最初の位置を特定します：
- 該当する位置が存在しない場合、
xはすべての末尾値より大きいため、最長列の長さを1つ拡張します。 - 位置
kが存在する場合、tails[k]をxで置き換えます。長さは変わりませんが、末尾値が小さくなる（または等しくなる）ことで、将来の拡張の選択肢が狭まることはありません。 tailsは狭義単調増加であるため、この位置はO(log L)時間で見つけることができます。
[3, 5, 6, 2] の場合、最初の3つの状態は [3]、[3, 5]、[3, 5, 6] となります。最後の 2 が最初の位置を置き換え、[2, 5, 6] となります。長さ自体は正しいままですが、入力において 2 は 5 や 6 よりも後に出現します。これが、tails を直接返してはならない反例です。
経路復元には2つのインデックス構造が必要です。tailsIndices[k] は、長さ k + 1 の最小末尾値を現在実現している入力位置を保持します。nums[i] が位置 k に配置されたとき、previous[i] を tailsIndices[k - 1] に設定します。その直前要素は i より前に現れ、かつ厳密に小さい値を持ちます。その後に末尾値が置き換えられても、既に書き込まれた直前リンクが変更されることはありません。最終的な最長末尾から後方に向かって復元を行います。
export function longestIncreasingSubsequence(nums: number[]): number[] {
if (nums.length === 0) return []
const tails: number[] = []
const tailsIndices: number[] = []
const previous = new Array<number>(nums.length).fill(-1)
for (let index = 0; index < nums.length; index += 1) {
const value = nums[index]
let left = 0
let right = tails.length
while (left < right) {
const middle = left + Math.floor((right - left) / 2)
if (tails[middle] < value) left = middle + 1
else right = middle
}
const lengthIndex = left
if (lengthIndex > 0) {
previous[index] = tailsIndices[lengthIndex - 1]
}
if (lengthIndex === tails.length) {
tails.push(value)
tailsIndices.push(index)
} else {
tails[lengthIndex] = value
tailsIndices[lengthIndex] = index
}
}
const result = new Array<number>(tails.length)
let index = tailsIndices[tails.length - 1]
for (
let resultIndex = result.length - 1;
resultIndex >= 0;
resultIndex -= 1
) {
result[resultIndex] = nums[index]
index = previous[index]
}
return result
}正当性は3つの要素から成り立ちます。第1に、tails は常に狭義単調増加を保ちます。より長い増加列から最後の要素を取り除くと、末尾がより小さい短い増加列が残るためです。第2に、二分探索による置き換えは、各長さで実現可能な最小の末尾値を維持します。これにより、架空の長い列を作り出すことなく、将来の拡張性を向上させます。第3に、各 tailsIndices[k] は長さ k + 1 のチェーンを実現しており、直前インデックスと値は狭義単調増加します。したがって、tails.length が真の最適値を超えることはなく、また任意の実在する LIS を走査すれば構造は必ず少なくともその長さに到達します。復元された直前チェーンは有効な最適解となります。
各要素は最大 L 個の末尾に対して1回の二分探索を行うため、計算時間は O(n log L) となり、一般的な上限表記では O(n log n) となります。3つの配列は O(n) の空間を使用し、出力配列自体は O(L) を使用します。このアルゴリズムは入力をソートせず、数値の範囲にも依存しません。
テストでは、長さ、狭義単調増加性、および入力インデックスの順序を検証する必要があります：
const cases: Array<[number[], number]> = [
[[10, 9, 2, 5, 3, 7, 101, 18], 4],
[[0, 1, 0, 3, 2, 3], 4],
[[7, 7, 7, 7], 1],
[[5, 4, 3, 2, 1], 1],
[[], 0],
]
for (const [nums, expectedLength] of cases) {
const result = longestIncreasingSubsequence(nums)
if (result.length !== expectedLength) throw new Error("wrong length")
for (let i = 1; i < result.length; i += 1) {
if (result[i - 1] >= result[i]) throw new Error("not increasing")
}
}より強固な検証として、長さ12以下のランダム配列を生成し、最適化された結果の長さを O(n²) の DP オラクルと比較します。また、返された値が入力内で順番に出現していることも線形走査で検証すべきです。これらの検証を組み合わせることで、重複境界のバグ、誤った二分探索条件、壊れた直前リンクをあぶり出すことができます。
高品質な模範解答
「まず、厳密な単調増加順であること、および実際の部分列を返す必要があることを確認します。2乗の解法では、dp[i] を nums[i] で終わる最善の長さとして定義し、それより前のすべての要素を確認します。その過去への走査を排除するために、各長さについて実現可能な最小の末尾値を保持します。
ある値 x に対し、x 以上の最初の末尾値を見つけます。存在しない場合、x は現在の最長列を拡張します。存在する場合、その末尾値を x で置き換えることで、同じ長さに対してより拡張しやすい（または同等の）末尾値を提供します。狭義単調増加であるためこの lower-bound の位置が必要となり、重複値は拡張ではなく置き換えとなります。
末尾配列の値は各長さの最善の終端を要約したものであり、入力インデックスとして整合しているとは限りません。実際の答えを返すため、tailsIndices[k] に長さ k + 1 の現在の末尾インデックスを記録します。要素が位置 k に入る場合、その直前要素は tailsIndices[k - 1] となります。走査完了後、最長末尾から直前リンクを辿り、後ろから出力を埋めます。
不変条件として、すべての末尾値はその長さにおいて実現可能な最小値であり、すべての末尾インデックスは実在する直前チェーンを持ちます。置き換えによって既存の長さが消えることはなく、将来の拡張性が向上するのみです。逆に、任意の実在する増加部分列の各要素を走査すると、構造は必ず少なくともその長さに到達するため、最終的な長さは最適となります。要素あたり1回の二分探索により時間計算量は O(n log n) となり、インデックスと直前配列の空間計算量は O(n) です。空配列、重複値、昇順、降順の入力をテストし、さらにランダムな小規模配列を2乗DPオラクルと比較検証します。」
よくある間違い
- 部分列を連続した部分配列として扱ってしまう → スライディングウィンドウでは要素のスキップができません → 増加する入力インデックスによって答えを定義してください。
- 解く前に入力をソートしてしまう → ソートすると元の相対順序が破壊されます → 値は入力順のまま処理してください。
dp[i]をプレフィックスの最適値として定義し直接遷移させてしまう → その最適値の末尾が現在の値を受け入れられない可能性があります → 状態は必ずiで終わるように定義してください。- 狭義増加バリアントで、値より厳密に大きい最初の末尾を探索してしまう → 重複値によって誤って長さが拡張されてしまいます → 値以上の最初の末尾を探索してください。
tailsを直接返してしまう → 末尾配列の値は入力インデックスが減少順になっている可能性があります → 末尾インデックスと直前リンクを用いて復元してください。- 末尾の置き換え後に過去の直前リンクを上書きしてしまう → 以前の有効なパスが破壊されます → 各直前リンクは一度割り当てたら変更しないでください。
- 末尾配列がソートされていることだけを証明する → ソートされていることだけでは最適な長さの証明になりません → 実現可能な最小末尾の不変条件と、長さの上限・下限の両方を証明してください。
- 二分探索＋配列挿入を
O(log n)と呼んでしまう → 中間への挿入は要素のシフトが発生します → インプレースの置き換え、または末尾への追加のみを行ってください。 - 古典的な代表例のみを実行する → 重複値や直前リンクのバグが見落とされます → 全要素同一、降順、空配列、およびランダムオラクルテストを使用してください。
- 特定企業での高い出題頻度を主張する → 公開問題ページは頻度や帰属を証明するものではありません → 検証済みの問題とアルゴリズムの価値のみを述べてください。
フォローアップと回答
フォローアップ1: 最長非減少部分列（広義単調増加）にするには何を変更しますか？
等しい値でも列を拡張できるようになります。二分探索の境界を value より厳密に大きい最初の位置（右側の挿入ポイント）に変更します。直前リンク、復元処理、および計算量は同じままです。二分探索の境界を変更せずに最後の比較条件だけを変更すると、重複値で破綻します。
フォローアップ2: 長さのみを返す場合、空間を削減できますか？
はい。tailsIndices と previous を削除し、L 個の最小末尾値のみを保持することで O(L) 空間に削減できます。時間計算量は O(n log L) のままです。部分列自体を返す場合はすでに出力に O(L) が必要であり、この1パス復元では各入力位置の直前情報を使用します。
フォローアップ3: 最長増加部分列の総数をカウントするにはどうしますか？
最小末尾配列は同じ長さの複数のパスを統合してしまうため、直接カウントを復元することはできません。シンプルな解法としては、length[i] と count[i] を保持します。より長いパスが見つかった場合は直前のカウントをコピーし、同じ長さのパスが見つかった場合はカウントを加算することで、O(n²) 時間で計算します。より大きな入力に対しては、座標圧縮を行い、最大長とカウントのペアを保持する Fenwick 木やセグメント木を使用し、重複カウントを避けるための厳密なマージルールを適用します。
フォローアップ4: 値が追加のみのストリーム（append-only stream）で到着する場合はどうなりますか？
現在の LIS の長さはオンラインで計算可能です。到着する各値に対して tails を O(log L) 時間で二分探索します。実際の列が必要な場合はインデックスと直前リンクを保持します。古い値を削除できる場合は、最小末尾が削除されたデータに依存する可能性があるため、このアルゴリズムではローカルに状態を巻き戻すことができず、動的構造やオフライン分解が必要になります。
フォローアップ5: 各要素に重みがあり、合計重みの最大化を目指す場合はどうなりますか？
同じ末尾の範囲であっても累積された重みが異なる可能性があるため、最小末尾値だけでは状態を要約できなくなります。値を座標圧縮し、Fenwick 木またはセグメント木に対してより小さい値の中で最善の重みをクエリし、現在の重みを加えて現在の座標を更新します。狭義および非減少バリアントではクエリ境界が異なります。計算時間は O(n log n) です。
フォローアップ6: このコードは辞書順最小の最適解を返しますか？
辞書順最小であることは保証されません。置き換えルールは個々の末尾値を最小化しますが、完全な最適パス間の安定した順序を定義するものではありません。1つのアプローチとして、各インデックスがサポートできる最適なプレフィックスまたはサフィックスの長さを計算し、最適長の解を完了できる値を貪欲に選択する方法があります。「値が最小の列」と「インデックスが最小の列」は異なる要件であるため、最初にどちらの辞書順が意図されているかを明確にしてください。