最大の区間和 キュー

今回は paiza の「最大の区間和　キュー」の問題に挑戦！

🟦 問題概要

🔹 テーマ

• 数列の 連続 X 個の区間
• その 和の最大値 を求める
• さらにその区間の 左端の値 も出力

🔹 やること

• 数列 A が与えられる
• 長さ X の連続区間をすべて調べる
• 各区間の合計を計算
• 最大の合計を見つける
• その区間の「左端の値」も出力

🔹 条件

• N ≤ 500,000（かなり大きい）
• X ≤ N
• 区間が複数同じ最大値の場合
  → 最も左にある区間を採用
  
  
  

入力例：

4 2
2 3 4 1

出力例：

7 3

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [N, X] = lines[0].split(' ').map(Number);
    const A = lines[1].split(' ').map(Number);

    const queue = [];
    let currentSum = 0;
    let maxSum = -Infinity;
    let leftValue = 0;

    for (let i = 0; i < N; i++) {

        // ① 新しい要素をキューへ追加
        queue.push(A[i]);
        currentSum += A[i];

        // ② X 個を超えたら古い要素を削除
        if (queue.length > X) {
            currentSum -= queue[0];
            queue.shift();
        }

        // ③ ちょうど X 個になったら判定
        if (queue.length === X) {
            if (currentSum > maxSum) {
                maxSum = currentSum;
                leftValue = queue[0]; // ← 区間の左端
            }
        }
    }

    console.log(maxSum, leftValue);
});

🔍コードの流れ

🔹 初期化

• 入力を受け取る
• N と X を取得
• 数列 A を配列として取得
• 空のキュー queue を用意
• 現在の合計 currentSum を用意
• 最大値 maxSum を用意

🔹 ループ処理（0 〜 N-1）

各 A[i] について：

• A[i] をキューに追加（push）
• 合計に A[i] を足す
• キューの長さが X を超えたら
  • 先頭の値を合計から引く
  • 先頭を削除（shift）
• キューの長さがちょうど X のとき
  • 合計を最大値と比較
    • 大きければ更新
    • そのときの queue[0] を左端として保存

🔹 最後

• 最大値と左端を出力

📝まとめ

🔹 ① スライディングウィンドウ

• 連続区間問題の基本パターン
• 「全部足す」から「差分更新」へ

🔹 ② キューの役割

• 直近 X 個を保持
• queue[0] が左端になる