【連続列】最長減少連続部分列

今回は paiza のDPで「【連続列】最長減少連続部分列」の問題に挑戦！

問題概要

• 入力
  • 1行目に人数 n
  • 2行目以降に、それぞれの人の身長 a_1, a_2, …, a_n（整数）が与えられる。

• 用語定義
  • 区間 [l, r] が 逆背の順 であるとは、
    任意の l ≤ i < r に対して a_i ≥ a_{i+1} が成り立つこと
  • 区間の長さ = r – l + 1

• 目的
  • 逆背の順であるような区間のうち、最長の長さを求める。

• 出力
  • その最大長

入力例：

5
187
192
115
108
109

出力例：

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

• 入力読み込み
  • n は人数
  • a は身長配列（1-indexにしたいので a.unshift(0) で先頭にダミーを入れる）

• DP配列 dp
  • dp[i] = 「人 i を右端とする逆背の順区間の長さ」
  • 初期値 dp[1] = 1（1人だけの区間）

• 漸化式
  • a[i-1] >= a[i] なら、前の区間を延長できる → dp[i] = dp[i-1] + 1
  • そうでなければ、長さは 1 にリセット

• 結果出力
  • Math.max(…dp.slice(1)) で最大長を求める

🗒️ まとめ

• 最長の「現象」連続区間の長さを求める

• 「逆背の順」＝左から右へ身長が減少または同じ

• DP：

  • dp[i] = i番目を右端とする逆背区間の長さ
  • a[i-1] >= a[i] →→ dp[i] = dp[i-1] + 1、それ以外は 1

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