paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 最長の区間

最長の区間 (paizaランク B 相当)

しゃくとり法で解きます。

区間の左端と
右端の更新条件は次の通りになります。
区間の総和が M を超えたとき : 左端++
区間の総和が M 以下のとき : 右端++

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

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

const [N, M] = lines[0].split(" ").map(Number);
let sum = 0;//区間和
let ans = 0;//最長の区間の長さ
let l = 0;//左端
let u = 0;//右端

const A = lines[1].split(" ").map(Number);

sum += A[0];

while (1) {
    //区間の総和が M を超えたとき : 左端++
    if (M < sum) {
        sum -= A[l];
        l++;
    //区間の総和が M 以下のとき : 右端++
    } else { // (sum < M)
        u++;
        ans = Math.max(ans, u-l);
        if (u === N) {//右端が全区間の右端に到達したら抜ける
            break;
        }else{
            sum += A[u];    
        }
        
    } 
}//while
console.log(ans);

解答例(Python3の場合参考)

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

const [n, m] = lines[0].split(" ").map(Number);
const numbers = lines[1].split(" ").map(Number);

let sums = [0];//累積和
for (let i = 0; i < n; i++) {
    sums.push(sums[i] + numbers[i]);
}

let count = 0;//最長の区間の長さ
let start = 0;//左端
let end = 0;//右端

while (true) {
    if (end >= n) {//全区間調べ終わったら抜ける
        break;
    }
    //区間の総和が M 以下のとき : 右端++
    if (sums[end + 1] - sums[start] <= m) {//区間和を累積和で計算
        //最長を更新
        if (end - start + 1 > count) {
            count = end - start + 1;
        }
        end += 1;//左端を進める
    //区間の総和が M を超えたとき : 左端++
    } else {
        start += 1;//右端を進める
    }
}//while

console.log(count);

解答例(Ruby の場合を参考に)

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

const [n, m] = lines[0].split(" ").map(Number);
const a = lines[1].split(" ").map(Number);

let [head, tail] = [0, 0];//右端、左端
let [sum, ans] = [0, -1];//区間和、答え

while (true) {
    //区間の総和が M 以下のとき : 右端++
    if (sum <= m) {
        ans = Math.max(ans, head - tail);//最長更新
        //調べ終わったら抜ける
        if (head === n) {
            break;
        }
        
        sum += a[head];
        head += 1;
    //区間の総和が M を超えたとき : 左端++
    } else {
        sum -= a[tail];
        tail += 1;
    }
}//while
 
console.log(ans);