paizaラーニング レベルアップ問題集 DPメニュー JavaScript 【部分列】最長減少部分列

【部分列】最長減少部分列 (paizaランク B 相当)

解答例

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n] = lines[0].split(" ").map(Number);
const a = lines.slice(0).map(Number);//木iとa[i]をそろえた
a[0] = 0;//木0は0としておく。

const dp = Array(n + 1).fill(0);//dp[i]は最後が木 i であるような増加部分列のうち最長であるものの長さ。これを登録していく。nまでなので長さn+1のArray(n+1)にする。

dp[1] = 1;//木iのdp[1]は1
for (let i = 2; i <= n; i++) { //木2から木nまで見ていく
  //木iに注目する
  dp[i] = 1; // 木 i のみからなる部分列の長さ
  //木iと、より小さい木jの高さを比較していく
  for (let j = 1; j <= i - 1; j++) { //a[j]はa[i]より小さい添字の木
    if (a[j] > a[i]) { //もし木jが木iより大きかったら
      //dp[i]は、最後が木i であるような増加部分列のうち最長であるものの長さ
      dp[i] = Math.max(dp[i], dp[j] + 1); // 最後が木 j であるような増加部分列の末尾に木 i をくっつける → dp[j] + 1
      //Math.max(dp[i], dp[j] + 1)の dp[i]は、最後が木iであるような増加部分列の今まで更新してきた中で一番長い長さ
      //dp[j] + 1は最後が木 j であるような増加部分列の末尾に木 i をくっつけた長さ
      //dp[j]は木jによって変わり、常にdp[j]+1>dp[i]ではないので、dp[i]と大きさを比較する必要があるからMath.max()
    }
  }
}
console.log(dp.reduce((a, b) => Math.max(a, b)));