連続列《DP・漸化式》

DPメニュー【最長増加連続部分列・最長減少連続部分列】

問題【STEP: 1】最長増加連続部分列
Task
n 人が並んでいます。背の順であるような区間のうち 最長は?

【最長増加連続部分列】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const a = [];  // 身長
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));
   }
   const dp = [1];  // a の値が昇順になっている区間
   for (let i = 1; i < n; i++) {
      a[i - 1] <= a[i] ? dp[i] = dp[i - 1] + 1 :  dp[i] = 1;
// a[i]の1つ前の値がa[i]以下なら dp[i]の値は dp[i - 1] + 1 そうじゃなければ 1
      // const [a, b] = [lines[i], lines[i + 1]];  // 配列を作らずに値を a, b で受取り
      // a <= b ? dp[i] = dp[i - 1] + 1 : dp[i] = 1;  // a, b を比較して dp の値を更新
   }
   console.log(Math.max(...dp));
});
hogeちゃんの画像

a[i] が a[i – 1]以上なら dp[i] = dp[i – 1] + 1, そうじゃなければ dp[i] = 1。

top
問題【FINAL】最長減少連続部分列
Task
n 人が並んでいます。逆背の順であるような区間のうち 最長は?

【最長減少連続部分列】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const a = [];  // 身長
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));
   }
   const dp = [1];  // a の値が昇順になっている区間
   for (let i = 1; i < n; i++) {
      a[i - 1] >= a[i] ? dp[i] = dp[i - 1] + 1 :  dp[i] = 1;
// a[i]の1つ前の値がa[i]以上なら dp[i]の値は dp[i - 1] + 1 そうじゃなければ 1
      // const [a, b] = [lines[i], lines[i + 1]];  // 配列を作らずに値を a, b で受取り
      // a >= b ? dp[i] = dp[i - 1] + 1 : dp[i] = 1;  // a, b を比較して dp の値を更新
   }
   console.log(Math.max(...dp));
});
hogeちゃんの画像
a[i] が a[i – 1]以下なら dp[i] = dp[i – 1] + 1, そうじゃなければ dp[i] = 1。
top

コメント