C++でインデックス間隔がk以上の最大合計部分列を求めるアルゴリズム

問題概要

サイズnの配列arr[]と整数kが与えられたとき、選んだ要素同士のインデックスがk以上離れている部分列の中で、合計が最大になるものを求めるプログラムを作成します。

問題の詳細

配列から要素を選んで部分列を構成します。このとき、選ばれた要素のインデックス同士は互いにk以上の距離を持つ必要があります。その条件を満たすすべての部分列の中から、合計値が最大となるものを見つけましょう。

入力例

arr[] = {2, 3, 7, 9, 2, 8, 3}

出力例

15

解説

条件を満たす部分列の例は以下の通りです。

{2, 9, 3} → 合計 = 14
{3, 2} → 合計 = 5
{7, 8} → 合計 = 15

この中で最大の合計値は15となります。

解法アプローチ

1. 単純な解法（全列挙）

最も基本的な方法は、条件を満たすすべての部分列を列挙し、それぞれの合計を計算して最大値を返すことです。しかし、部分列の候補数は組み合わせ爆発的に増加するため、配列が大きくなると現実的な時間内に計算できません。

2. 動的計画法（DP）による効率的な解法

効率を改善するには、動的計画法を活用します。「現在の位置までの最大合計」を格納する配列を用意し、配列の後ろから順に計算を進めます。

各要素iに対して、以下の2つの選択肢を比較します。

• 要素を合計に採用する場合： sum[i] = arr[i] + sum[i + k + 1]
• 要素を合計から除外する場合： sum[i] = sum[i + 1]

この2つのうち大きい方をsum[i]として記録し、最終的な答えとしてsum[0]を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

int calcMaxSubSeqSum(int arr[], int N, int k){
    int maxSumDP[N];
    maxSumDP[N - 1] = arr[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (i + k + 1 >= N)
            maxSumDP[i] = max(arr[i], maxSumDP[i + 1]);
        else
            maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]);
    }
    return maxSumDP[0];
}

int main() {
    int N = 10, k = 2;
    int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
    cout << "The maximum sum subsequence with at-least k distant elements is " << calcMaxSubSeqSum(arr, N, k);
    return 0;
}

実行結果

The maximum sum subsequence with at-least k distant elements is 230

計算量の評価

この動的計画法による解法は、配列を後ろから一度だけ走査するため、時間計算量はO(N)です。また、最大合計を保持する補助配列が必要なため、空間計算量もO(N)となります。全列挙を行う単純な解法と比べて大幅な高速化が実現でき、大きな入力に対しても実用的に動作します。