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}

アルゴリズム

• presum配列を作成します。これには、指定された配列の「index」から「index+K」までのすべての要素の合計が各インデックスに含まれます。また、合計配列のサイズはn + 1-k
になります。
• サイズkのサブアレイを含めると、重複するサブアレイが作成されるため、そのサブアレイの要素を他のサブアレイに再度含めることはできません。したがって、含まれているサブ配列のk個の要素を除外して再帰呼び出しを行います
• サブアレイを除外すると、そのサブアレイの次のk-1要素を他のサブアレイで使用できるため、そのサブアレイの最初の要素を除外するだけで再帰呼び出しを行うことができます。
• 最後に最大値（含まれる合計、除外される合計）を返します

例

#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