C++プログラム：配列内で要素間の距離がK未満にならない部分列の最大合計を求める方法

この問題では、サイズnの配列arr[]と整数kが与えられます。求めるのは、配列内でどの2つの要素も距離がk未満にならないように選んだ部分列（サブシーケンス）の合計の最大値です。

問題の概要

配列から要素を選んで部分列を作るとき、選んだ任意の2つの要素のインデックス差がk以上になるようにする必要があります。その制約のもとで、部分列の要素の合計が最大になる組み合わせを見つけるのが目的です。

入力例

arr[] = {6, 2, 5, 1, 9, 11, 4}
k = 2

出力例

16

説明

条件を満たす部分列の候補：
{6, 1, 4} → 合計 = 11
{2, 9} → 合計 = 11
{5, 11} → 合計 = 16
{1, 4} → 合計 = 5
...
最大合計 = 16

解法アプローチ：動的計画法（DP）

この問題は動的計画法を使うことで効率的に解けます。DP[i]には「i番目の要素までを考慮したときの、条件を満たす部分列の最大合計」を格納します。

i番目の要素について、「現在の要素arr[i]を部分列に加えることで合計が増えるかどうか」を判定します。具体的には、直前のDP値と「k+1個前までのDP値＋現在の要素」を比較します。

if( DP[i − (k+1)] + arr[i] > DP[i − 1] )
→ DP[i] = DP[i − (k+1)] + arr[i]
それ以外の場合 → DP[i] = DP[i−1]

最終的に、DP配列の中で最も大きい値が答えとなります。

アルゴリズムの手順

初期化

maxSumSubSeq = −1、maxSumDP[n]

ステップ1

maxSumDP[0] = arr[0] と初期化する。

ステップ2

i を 1 から n−1 までループさせる。

ステップ2.1

i < k の場合：
maxSumDP[i] = max(arr[i], maxSumDP[i−1])

ステップ2.2

それ以外の場合：
maxSumDP[i] = max(arr[i], maxSumDP[i − (k+1)] + arr[i])

ステップ3

maxSumDPの全要素から最大値を求め、maxSumSubSeqに格納する。

ステップ4

maxSumSubSeq を返す。

C++による実装例

#include <iostream>
using namespace std;

int retMaxVal(int a, int b){
    if(a > b)
    return a;
    return b;
}

int calcMaxSumSubSeq(int arr[], int k, int n) {
    int maxSumDP[n];
    int maxSum = −1;
    maxSumDP[0] = arr[0];
    for (int i = 1; i < n; i++){
       if(i < k ){
          maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − 1]);
       }
       else
       maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − (k + 1)] + arr[i]);
   }
    for(int i = 0; i < n; i++)
    maxSum = retMaxVal(maxSumDP[i], maxSum);
    return maxSum;
}

int main() {
    int arr[] = {6, 2, 5, 1, 9, 11, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout<<"配列内で2つの要素が距離 "<<k<<" 未満にならないような部分列の最大合計は "<<calcMaxSumSubSeq(arr, k, n);
    return 0;
}

実行結果

配列内で2つの要素が距離 2 未満にならないような部分列の最大合計は 16

計算量の分析

このアルゴリズムの時間計算量はO(n)です。配列を一度走査してDPテーブルを埋め、もう一度走査して最大値を求めるだけだからです。空間計算量もO(n)で、DPテーブルの分だけ追加メモリが必要になります。貪欲法では局所最適解に陥る可能性があるため、この種の「間隔制約付き最大化問題」では動的計画法が有効なアプローチとなります。