C++でサイズKの重複しないM個の部分配列の最大合計を求める方法

問題文

配列と2つの数値 M・K が与えられます。このとき、配列の中からサイズ K の重複しない部分配列を選び、そのうち最大 M 個の合計値を求めることが課題です(配列の要素の順序は変更されません)。

ここで、K は部分配列のサイズ、M は選ぶ部分配列の個数を表します。配列のサイズは m × k より大きいものと仮定して構いません。また、配列全体のサイズが k の倍数でない場合は、末尾の部分配列を部分的に採用することも可能です。

入力例

たとえば、配列が {2, 10, 7, 18, 5, 33, 0}、N = 7、M = 3、K = 1 である場合を考えます。このとき選択される部分集合は次の通りです。

{33, 18, 10}

そのため、出力される最大合計は 61 となります。

アルゴリズム

• まず presum(累積和)配列 を作成します。各インデックスには、元の配列の「index」から「index + K − 1」までの全要素の合計が格納されます。この presum 配列のサイズは n + 1 − k になります。
• サイズ k の部分配列を採用する場合、その部分配列に含まれる要素を他の部分配列で再利用することはできません(部分配列同士が重なってしまうため)。そこで、採用した部分配列の k 個の要素をすべて除外した位置から再帰呼び出しを行います。
• 逆に部分配列を採用しない場合は、その部分配列の先頭以外の k − 1 個の要素を他の部分配列に使用できるため、先頭の1要素だけを除外した位置から再帰呼び出しを行います。
• 最後に、「採用した場合の合計」と「採用しなかった場合の合計」のうち大きい方(max)を返します。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
void calculatePresumArray(int presum[], int arr[], int n, int k) {
   for (int i = 0; i < k; i++) {
      presum[0] += arr[i];
   }
   for (int i = 1; i <= n - k; i++) {
      presum[i] += presum[i-1] + arr[i+k-1] - arr[i- 1];
   }
}
int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
   if (m == 0)
      return 0;
   if (start > size - 1)
      return 0;
   int mx = 0;
   int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
   int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
   return max(includeMax, excludeMax);
}
int main() {
   int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
   int n = sizeof(arr)/sizeof(arr[0]);
   int m = 3, k = 1;
   int presum[n + 1 - k] = { 0 };
   calculatePresumArray(presum, arr, n, k);
   cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
   return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力結果

Maximum sum = 61