【C++】配列内のK番目ごとの要素を取得したときの最大合計を求める方法

この記事では、配列 arr[] と整数 k が与えられたとき、「K番目ごとの要素を取得して得られる合計」の最大値を求めるアルゴリズムについて解説します。

問題の概要

配列の要素のうち、インデックスが k ずつ離れている要素だけを選んで合計し、その合計が最大になるようにします。つまり、次の式で表される sum を最大化することが目的です。

sum = arr[i] + arr[i+k] + arr[i+2*k] + … + arr[i+p*k]（条件：i + p*k < n）

入出力例

入力：

arr[] = {5, 3, −1, 2, 4, −5, 6}, k = 4

出力：

9

説明：

各開始位置から k 個おきに要素を取得した場合の合計は以下のようになります。

5 + 4 = 9
3 − 5 = −2
−1 + 6 = 5
2
4
−5
6

これらの中で最大となるのは 9 です。

解法アプローチ①：二重ループによるシンプルな解法（計算量 O(n²)）

最も単純な方法は、外側のループで各開始位置 i を走査し、内側のループで「i から始めて k 個おきに要素を加算した合計」を計算する方法です。すべての開始位置について合計を求め、その中の最大値を返します。

実装例

#include <iostream>
using namespace std;

int findMaxSumK(int arr[], int n, int K){
    int maxSum = -1000;
    for (int i = 0; i < n; i++) {
        int current_Sum = 0;
        for (int j = i; j < n; j += K)
            current_Sum += arr[j];
        maxSum = max(maxSum, current_Sum);
    }
    return maxSum;
}

int main(){
    int arr[] = {5, 3, -1, 2, 4, -5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    cout << "配列内のK番目ごとの要素を取得したときの最大合計は "
         << findMaxSumK(arr, n, K);
    return (0);
}

出力

配列内のK番目ごとの要素を取得したときの最大合計は 13

この方法は直感的で分かりやすい反面、すべての開始位置に対して再度合計を計算するため、時間計算量は O(n²) となり、配列が大きい場合は非効率です。

解法アプローチ②：接尾辞和（Suffix Sum）を使った効率的な解法（計算量 O(n)）

より効率的な方法として、接尾辞和 を利用する手法があります。これは、各位置 i から「k 個おきに要素を取得した合計」を後ろから順に計算していく方法です。

具体的には、次の漸化式に従って配列 suffSum[] を埋めていきます。

• i + K < n の場合：suffSum[i] = suffSum[i + K] + arr[i]
• それ以外の場合：suffSum[i] = arr[i]

このようにすると、各位置からの合計を一度の走査で求められるため、時間計算量は O(n) に抑えられます。

実装例

#include <iostream>
using namespace std;

int findMaxSumK(int arr[], int n, int K) {
    int maxSum = -1000;
    int suffSum[n];
    for (int i = n - 1; i >= 0; i--) {
        if (i + K < n)
            suffSum[i] = suffSum[i + K] + arr[i];
        else
            suffSum[i] = arr[i];
        maxSum = max(maxSum, suffSum[i]);
    }
    return maxSum;
}

int main(){
    int arr[] = {5, 3, -1, 2, 4, -5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    cout << "配列内のK番目ごとの要素を取得したときの最大合計は "
         << findMaxSumK(arr, n, K);
    return (0);
}

出力

配列内のK番目ごとの要素を取得したときの最大合計は 13

まとめ

小さな配列であれば二重ループでも十分ですが、パフォーマンスが重要な場面では接尾辞和を利用した O(n) の解法を採用するのがおすすめです。どちらのコードも同じ結果を出力するため、用途や制約に応じて使い分けましょう。