累積和メニュー【連続する N 個の和の最大値 1 〜 4】
【連続する N 個の和の最大値 1】コード
const a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]; // 元の数値
const s = [0]; // a の 累積和
for (let i = 0; i < 10; i++) {
s.push(s[i] + a[i]); // s[i+ 1] は s[i] + a[i]
}
// s = [0, 1, 6, 15, 22, 27, 30, 32, 37, 45, 49]
const sum_3 = []; // a の 連続する 3 個の整数の和
for (let i = 0; i <= 7; i++) {
sum_3.push(s[i + 3] - s[i]); // sum_3[i] は s[i+1]~s[i+3]の和
}
// sum_3 = [15, 21, 21, 15, 10, 10, 15, 17]
console.log(Math.max(...sum_3)); // sum_3 を展開して 最大値を出力
連続する 3 個の整数の和の最大値 は s[i + 3] - s[i]
。Math.max(...sum)
で sum の最大値が取得できました。
【連続する N 個の和の最大値 2】コード
reader.on('close', () => {
const a = lines[0].split(' ').map(Number); // 元の数値
const s = [0]; // a の 累積和
for (let i = 0; i < 10; i++) {
s.push(s[i] + a[i]); // s[i+ 1] は s[i] + a[i]
}
const sum_3 = []; // a の 連続する 3 個の整数の和
for (let i = 0; i <= 7; i++) {
sum_3.push(s[i + 3] - s[i]); // sum_3[i] は s[i+1]~s[i+3]の和
}
console.log(Math.max(...sum_3)); // sum_3 を展開して 最大値を出力
});
配列 a の値を標準入力から受け取っていますが それ以外は 【STEP: 1】と同じです。
【連続する N 個の和の最大値 3】コード
reader.on('close', () => {
const N = Number(lines[0]);
const a = lines[1].split(' ').map(Number); // 元の数値
const s = [0]; // a の 累積和
for (let i = 0; i < N; i++) {
s.push(s[i] + a[i]); // s[i+ 1] は s[i] + a[i]
}
const sum_3 = []; // a の 連続する 3 個の整数の和
for (let i = 0; i <= N - 3; i++) {
sum_3.push(s[i + 3] - s[i]); // sum_3[i] は s[i+1]~s[i+3]の和
}
console.log(Math.max(...sum_3)); // sum_3 を展開して 最大値を出力
});
配列 a の 要素数が N 個になりましたが それ以外は【STEP: 2】と同じです。
【連続する N 個の和の最大値 4】コード
reader.on('close', () => {
const [N, K] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map(Number); // 元の数値
const s = [0]; // a の 累積和
for (let i = 0; i < N; i++) {
s.push(s[i] + a[i]); // s[i+ 1] は s[i] + a[i]
}
const sum_3 = []; // a の 連続する 3 個の整数の和
for (let i = 0; i <= N - K; i++) {
sum_3.push(s[i + K] - s[i]); // sum_3[i] は s[i+1]~s[i+K]の和
}
console.log(Math.max(...sum_3)); // sum_3 を展開して 最大値を出力
});
配列 a の 要素数が N 個。連続する 3 個の和の最大値が 連続する K 個の和の最大値になりましたが それ以外は【STEP: 3】と同じです。
コメント