paizaラーニング レベルアップ問題集 スタック・キューメニュー JavaScript 最大の区間和

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

解答例

タイムオーバーにならないように、区間をキューとして考えます。まず、先頭の区間和を求めます。次の区間和を計算するときに、先頭の区間から、先頭の要素をキューから出して、X+1目の要素をキューに入れてから、区間和を求めます。すなわち、次の区間和＝前の区間和ー前の区間の先頭の要素＋次の区間の末尾の要素です。すると、計算の手間が、通常ならばX回足すところ、２回で済みます。

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

const [N, X] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);

//初期値は左端からX個の区間
let left_num = A[0];//左端
//A に含まれる連続した X 個の要素の和
let sum_a = A.slice(0, X).reduce((a, b) => a + b);
let max_sum = sum_a;//最大値

//Aの中の区間X個を1要素ずつずらして計算する
for (let i = 1; i <= N - X; i++) {
  sum_a -= A[i - 1];//前区間の先頭要素
  sum_a += A[i + X - 1];//次区間の末尾要素
  //最大値更新
  if (sum_a > max_sum) {
    left_num = A[i];//左端
    max_sum = sum_a;//合計    
  }
}
console.log(max_sum, left_num);