最長部分増加列

今回は paiza のDPで「最長部分増加列」の問題に挑戦！

最長増加部分列 (Longest Increasing Subsequence, “LIS”)を求める問題！

問題概要

• 入力:
  • n 本の木
  • 各木の高さ a_1, a_2, ..., a_n

• 操作:
  • 一部の木を伐採してもよい
  • 残った木の高さが左から見て 単調増加（a_k1 < a_k2 < … < a_km） になるようにする

• 操作の目的:
  • 残った木の本数（= 最長増加部分列の長さ）を最大化する

• 出力:
  • 伐採せずに残る木の最大本数

入力例:

5
100
102
101
91
199

出力例:

3

✅ OK例：

const rl = require('readline').createInterface({ input:process.stdin });

const lines = [];

rl.on('line', (input) => lines.push(input));


rl.on('close', () => {
    const n = Number(lines[0]);
    const a = lines.slice(1).map(Number);
    a.unshift(0);
    
    const dp = [];
    dp[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        dp[i] = 1;
        
        for (let j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    console.log(Math.max(...dp.slice(1)));
});

🔍コードの解説

const n = Number(lines[0]); // 木の本数
const a = lines.slice(1).map(Number); // 木の高さを配列に
a.unshift(0); // 先頭にダミーを入れて 1-index にする

• a[1] ~ a[n] が木の高さ
• 1番目の木を a[1] にするために、a.unshift(0) でダミー要素を前に追加

const dp = [];
dp[1] = 1;

• dp[i] = 「木 i を最後にする増加部分列の最長 長さ」

• 1番目の木だけで作れる部分列は長さ 1 → dp[1] = 1

for (let i = 2; i <= n; i++) {
    dp[i] = 1;    // 木 i だけを選んだ場合の長さ = 1

• 各木 i を順番に見ていく
• まずは「木 i だけ」の場合を初期値として dp[i] = 1

        for (let j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

• i より前の木 j を全部チェック
• 条件: a[j] < a[i]
  → 木 j の高さより木 i が高ければ、
  「j で終わる増加列の末尾に i をつなげられる」
  • このとき長さは dp[j] + 1
    「複数の候補 j がある → 最長を選ぶ」ために max 比較が必須
• その中で最大値を取るのが dp[i]

console.log(Math.max(...dp.slice(1)));

• 全ての dp[i] の最大値が 最長増加部分列の長さ
• それを出力して終了

🔍 dpの流れ

入力

n = 5
a = [100, 102, 101, 91, 199]

dp[i] の意味

「1番目～i番目までを見たとき、a[i] を 末尾とする LIS の長さ」。

初期化

dp[1] = 1 // [100]

i = 2 のとき (a[2] = 102)

• j = 1: a[1] = 100 < 102 → 候補 = dp[1] + 1 = 2
• dp[2] = max(dp[1], dp[1]+1) = 2

dp = [1, 2]

部分列: [100, 102]

i = 3 のとき (a[3] = 101)

• j = 1 : a[1] = 100 < 101 → 候補 = dp[1] + 1 = 2
• j = 2 : a[2] = 102 > 101 → ダメ

よって dp[3] = 2

dp = [1, 2, 2]

部分列候補: [100, 101]

i = 4 のとき (a[4] = 91)

• j = 1 : 100 > 91 → ダメ
• j = 2 : 102 > 91 → ダメ
• j = 3 : 101 > 91 → ダメ

dp[4] = 1

dp = [1, 2, 2, 1]

部分列: [91]

i = 5 のとき (a[5] = 199)

• j = 1 : a[1] = 100 < 199 → 候補 = dp[1]+1 = 2
• j = 2 : a[2] = 102 < 199 → 候補 = dp[2]+1 = 3
• j = 3 : a[3] = 101 < 199 → 候補 = dp[3]+1 = 3
• j = 4 : a[4] = 91 < 199 → 候補 = dp[4]+1 = 2

最大は 3

dp = [1, 2, 2, 1, 3]

結果

max(dp) = 3

部分列の例: [100, 102, 199] または [100, 101, 199]

✅ この例で「j=3 のとき候補=3」「j=4 のとき候補=2」と分岐して、より長い経路を選ぶために max を取る必要があることがわかる。

🗒️ まとめ

• dp[i] = 「木 i を最後にしたときの LIS 長さ」

• dp[i] = 1 を初期値にして、前の木 j と i を比較
  • 木 j の高さより木 i が高ければ、
    「j で終わる増加列の末尾に i をつなげられる」
  • 「複数の候補 j がある → 最長を選ぶ」ために max 比較が必須

• 最終的な答えは max(dp)

僕の失敗談(´;ω;｀)と解決法🐈