【Java】連続するN個の和の最大値

問題

サイズnの配列aにおいて、連続するk個の要素の和の最大値を求めよ。

Javaのコードに使いやすいように一般化

1. 連続するk個の要素（区間）

   • a[0] ～ a[k-1]
   • a[1] ～ a[k]
   • a[2] ～ a[k+1]
   • ↓
   • a[i] ～ a[i+k-1]
     • 上記は、i番目の連続するk個の要素を指す。
       具体的に言うと、5番目の連続する3個の要素の場合、
       a[5] ～ a[5+3-1] = a[7] → a[5], a[6], a[7]
   • nを使った一般化は、下記の通り。
     a[n-k] ～ a[n-1]
     • 上記は、サイズnの最後の連続するk個の要素を指す。
       具体的に言うと、サイズ8の連続する3個の要素の場合、
       a[8-3] ～ a[8-1] = a[5], a[6], a[7]

2. 区間の和

   • 区間a[i] → a[j]の和 = s[j + 1] - s[i] ※従前の記事の「累積和と区間の和」より
   • ∴ 区間a[i] → a[i + k - 1]の和 = s[i + k] - s[i]

コード例

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 累積和の配列 s を作成
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + a[i];
        }
        

        // 暫定最大値を格納する変数 maxSum を 0 で初期化
        int maxSum = 0;
        // i を 0 から n-k まで繰り返す (nを使った一般化より)
        for (int i = 0; i < n - k + 1; i++) {
            // もし 区間の和であるs[i+k]-s[i] が maxSum より大きければ
            if (maxSum < s[i + k] - s[i]) {
                // maxSum を 区間の和 で更新
                maxSum = s[i + k] - s[i];
            }
        }
        // maxSum を出力
        System.out.println(maxSum);
    }
}

標準入力の入力値は下記の通り。

8 3
1 2 3 4 5 6 7 8

コード例の解説

今回はコード例の解説は行いません。
一般化について理解ができていれば、今回の肝である下記のコードを読むことは難しくないためです。

int maxSum = 0;

for (int i = 0; i < n - k + 1; i++) {
    if (maxSum < s[i + k] - s[i]) {
        maxSum = s[i + k] - s[i];
    }
}