C++で解く「K個以上離れた要素を選ぶ最大和部分列」問題

はじめに

このチュートリアルでは、「少なくともK個離れた要素からなる最大和部分列」を求めるプログラムについて解説します。動的計画法(DP)を活用することで、効率よく最適解を導き出すことができます。

問題の概要

整数を含む配列と値Kが与えられます。求めるのは、選ばれたどの2つの要素の間にも少なくともK個の要素が存在する(インデックスの差がK+1以上である)という制約を満たしながら、合計値が最大となる部分列です。

アルゴリズムの考え方

この問題は動的計画法で解くことができます。MS[i] を「インデックスi以降で選択可能な要素の合計の最大値」と定義し、配列を後ろから前に向かって走査していきます。

• i + k + 1 が配列の範囲外の場合： arr[i] を選ぶか、あるいは MS[i+1](arr[i] を選ばない場合)のいずれか大きい方を MS[i] とします。
• それ以外の場合： arr[i] を選んで MS[i+k+1] につなげるケースと、arr[i] をスキップして MS[i+1] につなげるケースを比較し、大きい方を採用します。

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;
// 最大和部分列を求める
int maxSum(int arr[], int N, int k) {
   int MS[N];
   MS[N - 1] = arr[N - 1];
   for (int i = N - 2; i >= 0; i--) {
      if (i + k + 1 >= N)
         MS[i] = max(arr[i], MS[i + 1]);
      else
         MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
   }
   return MS[0];
}
int main() {
   int N = 10, k = 2;
   int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
   cout << maxSum(arr, N, k);
   return 0;
}

実行結果

230

コードの解説

上記の例では、配列 { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 } に対して k = 2 として計算しています。このときの最適な選び方は、インデックス 1・4・8 の要素、すなわち 70 + 90 + 70 = 230 となります。隣り合う選択要素のインデックス差はそれぞれ 3 と 4 であり、いずれも k+1 以上であるため、距離の制約を満たしていることが確認できます。

計算量

• 時間計算量：O(N) — 配列を一度だけ走査すればよいため、非常に高速です。
• 空間計算量：O(N) — DPテーブル MS[] を保持するために必要となります。

まとめ

「K個以上離れた要素を選ぶ最大和部分列」問題は、配列を後ろから走査するDPによって線形時間で解くことができます。各位置で「その要素を選ぶか・選ばないか」を比較するシンプルな漸化式がポイントであり、同様の間隔制約付き最適化問題にも応用できる考え方です。