連続する N 個の和の最大値《累積和》

累積和メニュー【連続する 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 を展開して 最大値を出力
hogeちゃんの画像

連続する 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 を展開して 最大値を出力
});
hogeちゃんの画像

配列 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 を展開して 最大値を出力
});
hogeちゃんの画像

配列 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 を展開して 最大値を出力
});
hogeちゃんの画像

配列 a の 要素数が N 個。連続する 3 個の和の最大値が 連続する K 個の和の最大値になりましたが それ以外は【STEP: 3】と同じです。

コメント