C++で解説：配列内の要素間の距離がK未満にならない部分列の最大和を求める方法

このチュートリアルでは、配列内のどの2つの要素も互いに距離がK未満にならないように要素を選んだときの、部分列の最大合計値を求めるプログラムについて解説します。

N個の整数からなる配列と値Kが与えられます。私たちのタスクは、互いにK以上離れた位置にある要素だけを選んで構成した部分列のうち、合計値が最大になるものを見つけることです。

アルゴリズムの考え方（動的計画法）

この問題は、動的計画法（DP）を用いることで効率的に解くことができます。各インデックスiについて、「その位置までの要素を考慮したときの最大和」をdp[i]として順に記録していきます。

• 初期条件：dp[0] = arr[0]
• i ≤ k の場合：dp[i] = max(arr[i], dp[i-1])。距離K以内にある要素同士は同時に選べないため、それまでの累積最大値との大きい方を採用します。
• i > k の場合：dp[i] = max(arr[i], dp[i-(k+1)] + arr[i])。「現在の要素を選ばない場合」と「k+1個前までの最適解に現在の要素を加える場合」を比較して決定します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 最大和を返す関数
int maxSum(int* arr, int k, int n) {
    if (n == 0)
        return 0;
    if (n == 1)
        return arr[0];
    if (n == 2)
        return max(arr[0], arr[1]);
    int dp[n];
    dp[0] = arr[0];
    for (int i = 1; i <= k; i++)
        dp[i] = max(arr[i], dp[i - 1]);
    for (int i = k + 1; i < n; i++)
        dp[i] = max(arr[i], dp[i - (k + 1)] + arr[i]);
    int max = *(std::max_element(dp, dp + n));
    return max;
}
int main() {
    int arr[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxSum(arr, k, n);
    return 0;
}

出力

15

結果の解説

この例では、配列 {6, 7, 1, 3, 8, 2, 4} からインデックス1の「7」とインデックス4の「8」を選びます。両者の距離は3であり、K（=2）以上なので同時に選択できます。このときの合計は 7 + 8 = 15 となり、これが条件を満たす部分列の中での最大値となります。