paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 累積和の計算

累積和の計算 (paizaランク C 相当)

素直に書くと、

タイムーオーバー

for (let i = 0; i < N; i++) {
    let S = 0; //和S
    for(let j = 0; j < A.length; j++) {
		
        S += A[j];
	}
    console.log(S);
}

ですが、これだと計算量が多すぎてタイムオーバします。

解答例

上の解答では、和を求めるのに、毎回ループで計算していますが、
S[i] = S[i - 1] + A[i]の関係式を用いると、一発で求められます。
計算量を落とすのに使われます。
この問題のSを累積和と言います。
以下の解答では、累積和をつくりながら、出力しています。

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

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

let S = 0; //累積和S
for (let i = 0; i < N; i++) {
    S += A[i];
    console.log(S);
}