最長増加連続部分列

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

久しぶりにインデックスのズレでミスった(´;ω;｀)

問題概要

• 状況
  • n 人が横一列に並んでいる。
  • 左から i 番目の人を「人 i」と呼ぶ。
  • 人 i の身長は a_i [cm]。

• 「背の順区間」の定義 区間 [l, r] が「背の順」であるとは、
  • すべての l ≤ i < r について a_i ≤ a_{i+1} が成り立つこと。
  • 区間の長さは r – l + 1。
  • つまり、身長が非減少（同じか大きくなる）で並んでいる連続区間を指す。

• 求めるもの 背の順区間のうち、最も長いものの長さを求める。

入力例:

5
160
178
170
190
190

出力例:

3

❌NG例：

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);　//　ここが問題
    
    const dp = [];
    dp[1] = 1;
    
    for(let i = 2; i <= n; i++){
        if (a[i-1] <= a[i]) {
            dp[i] = dp[i-1] + 1
        }
        else {
            dp[i] = 1;
        }
    }
    
    console.log(Math.max(...dp.slice(1))); // 地味に大事
});

a[0] が1人目なのに、コードは a[i-1] <= a[i] で i を 1 始まりのつもりで使っているのでズレが発生。

✅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++){
        if (lines[i-1] <= lines[i]) {
            dp[i] = dp[i-1] + 1
        }
        else {
            dp[i] = 1;
        }
    }
    
    console.log(Math.max(...dp.slice(1)));
});

• DPの定義
  dp[i] = 「i番目の人を右端とする背の順区間の最長長さ」

• 初期条件
  dp[1] = 1（最初の人は自分だけの区間になる）

• 漸化式

もし a[i-1] <= a[i] なら、前の区間に人 i を追加できるので、

dp[i] = dp[i-1] + 1

そうでなければ、人 i だけの区間から始めるので、

dp[i] = 1

• 答え
  dp の最大値が答え。

📝考え方のまとめ

• 定義のポイント

  • dp[i] = 「人 i が右端になっている背の順区間のうち、最長の区間の長さ」

  • この定義により、「人 i の直前の人との関係」だけで dp[i] を決められる。

• 状態遷移

  もし a[i-1] ≤ a[i]
  → 前の区間に人 i を追加できるので
  dp[i] = dp[i-1] + 1

  もし a[i-1] > a[i]
  → 背の順が崩れるので、人 i だけの区間から再スタート
  dp[i] = 1

• 全体像

  • 左から順に dp を計算していく。

  • 各位置で「右端が自分の最長区間の長さ」がわかるので、答えは dp の最大値。