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

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

解答例

人の番号と、配列a、配列dpのインデックスを合わせた。
なので、配列a、配列dpの長さはn+1にした。

reduceとMath.maxで最大値を求めた。

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);//dpと長さn+1に揃えるのでslice(0)とした。
a[0] = 0;//a[0]は見た目上0にしておく。

const dp = Array(n + 1).fill(0);//ここに区間の最長の長さを登録していく。nまでなので長さn+1のArray(n+1)。

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(dp.reduce((a, b) => Math.max(a, b)));

解答例(C++の場合参考)

配列aは長さn+1,配列dpも長さn+1,aとdpのインデックスiと人i番目は一緒。
aの身長を見ていく時、i=1からにしている。

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 = Array(n+1);
a[0] = 0;//a[0]は身長0として,a[1]>=a[0]になるようにしている。
for(let i = 1; i <= n; i++){
    a[i] = lines[i];
}

const dp = Array(n + 1);//ここに区間の最長の長さを登録していく。nまでなので長さn+1のArray(n+1)。

dp[0] = 0;//dp[0]は長さなし
for(let i = 1; i <= n; i++){//aの身長i=1から見ていく
    if(a[i-1] >= a[i]){
        dp[i] = dp[i-1] + 1;
    }else{
        dp[i] = 1;
    }
}

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

解答例(Python3の場合参考)

実装上、aのsliceで、インデックスi-1とi番目の人が一緒。
なのでdpもインデックスi-1とi番目の人を一緒にした。

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(1).map(Number);

dp = Array(n).fill(1);//ここに区間の最長の長さを登録していく。１番目の人インデックス0で、初期値は1なのでfill(1)
for(let i = 1; i <= n; i++){
    if(a[i-1] >= a[i]){
        dp[i] = dp[i-1] + 1;
    }else{
        dp[i] = 1;
    }
}

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

解答例(Javaの場合参考)

aとdpのインデックスはi番目の人に合わせた。
dpは最後Math.maxで比較するので、fill(0)で初期化。
aは2から見ていく、前問の問題文の通り。

let answer以降は、reduceの動きをfor of　でループするやり方。

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 = Array(n+1);
a[0] = 0;//a[0]は身長0として,a[1]>=a[0]になるようにしている。
for(let i = 1; i <= n; i++){
    a[i] = lines[i];
}

const dp = Array(n + 1).fill(0);//ここに区間の最長の長さを登録していく。nまでなので長さn+1のArray(n+1)。最後比較するのでfill(0)で初期化。

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;
  }
}

let answer = 1;
for (let val of dp) {
  answer = Math.max(answer, val);
}
console.log(answer);