最長増加部分列（LIS）問題の詳細解析

Dynamic Programming Approach with Visualization

問題の概要

n本の木が横一列に並んでおり、何本かの木を伐採して残った木の高さが単調増加になるようにしたい。 残せる木の最大本数を求める問題です。これは最長増加部分列（Longest Increasing Subsequence, LIS）問題として知られています。

アルゴリズムの解説

📊 ステップ1: 問題の変換

配列 [100, 102, 101, 91, 199] から最長増加部分列を見つける

木1
100
木2
102
木3
101
木4
91
木5
199

🔢 ステップ2: DPテーブルの構築

dp[i] = i番目の木を最後とする最長増加部分列の長さ

木1 (100)
木2 (102)
木3 (101)
木4 (91)
木5 (199)
1
2
2
1
3

💻 ステップ3: コードの詳細解析

1function longestIncreasingSubsequence(n, heights) {
2  // dp[i] = i番目の木を最後とする増加部分列の最大長
3  // 初期値は全て1（各木単体の部分列）
4  const dp = new Array(n).fill(1);
5
6  // 各木について、その木を最後とする最長増加部分列の長さを計算
7  for (let i = 1; i < n; i++) {
8    // i番目の木より前の全ての木をチェック
9    for (let j = 0; j < i; j++) {
10      // j番目の木の高さがi番目の木の高さより小さい場合
11      if (heights[j] < heights[i]) {
12        // j番目の木を最後とする部分列にi番目の木を追加
13        dp[i] = Math.max(dp[i], dp[j] + 1);
14      }
15    }
16  }
17
18  // 全てのdp値の中で最大値を返す
19  return Math.max(...dp);
20}

計算量解析

⏱️ 時間計算量

O(n²)
  • • 外側のループ: n-1 回
  • • 内側のループ: 最大 n-1 回
  • • 総操作回数: 約 n²/2 回
  • • n=5,000 → 約 12,500,000 回

💾 空間計算量

O(n)
  • • dpテーブル: n 個の整数
  • • heightsテーブル: n 個の整数
  • • その他変数: 定数個
  • • 総メモリ: 約 8n バイト

実行過程の詳細

🚀 最適化バージョン（O(n log n)）

より大きなデータセットに対しては、二分探索を使用したO(n log n)のアルゴリズムも実装可能です。 

1function longestIncreasingSubsequenceOptimized(n, heights) {
2    // tails[i] = 長さi+1の増加部分列の末尾要素の最小値
3    const tails = [];
4    
5    for (let i = 0; i < n; i++) {
6        const height = heights[i];
7        
8        // 二分探索で挿入位置を見つける
9        let left = 0;
10        let right = tails.length;
11        
12        while (left < right) {
13            const mid = Math.floor((left + right) / 2);
14            if (tails[mid] < height) {
15                left = mid + 1;
16            } else {
17                right = mid;
18            }
19        }
20        
21        // 挿入または更新
22        if (left === tails.length) {
23            tails.push(height);
24        } else {
25            tails[left] = height;
26        }
27    }
28    
29    return tails.length;
30}