C++での配列の最大平均合計パーティション

問題の説明

配列が与えられた場合、数値Aの行を最大でK個の隣接する（空でない）グループに分割し、スコアは各グループの平均の合計になります。スコアリングできる最大スコアはいくつですか？

例

入力配列が{9、2、5、3、10}の場合、次のように配列を分割できます-

{9} {2、5、3}および{10}の場合、これの平均合計は-

9 +（2 + 5 + 3）/ 3 + 10 =22.33

アルゴリズム

この問題を解決するために暗記技術を使用することができます-

• メモ[i][k]を、A[iからn-1]を最大でK個のパーツに分割する最高のスコアとします
• 最初のグループでは、A[iからn-1]をA[iからj-1]とA[jからn-1]に分割し、候補の分割のスコアはaverage（i、j）+になります。スコア（j、k-1））、ここで、average（i、j）=（A [i] + A [i +1]+…+A[j-1]）/（j – i）。これらの中で最高のスコアを取ります
• 全体として、一般的な場合の再帰は次のとおりです。memo [n] [k] =max（memo [n] [k]、score（memo、i、A、k-1）+ average（i、j ））

例

例を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
define MAX 1000
double memo[MAX][MAX];
double score(int n, vector<int>& arr, int k) {
   if (memo[n][k] > 0) {
      return memo[n][k];
   }
   double sum = 0;
   for (int i = n - 1; i > 0; i--) {
      sum += arr[i];
      memo[n][k] = max(memo[n][k], score(i, arr, k - 1) + sum / (n - i));
   }
   return memo[n][k];
}
double getLargestSum(vector<int>& arr, int K) {
   int n = arr.size();
   double sum = 0;
   memset(memo, 0.0, sizeof(memo));
   for (int i = 0; i < n; i++) {
      sum += arr[i];
      memo[i + 1][1] = sum / (i + 1);
   }
   return score(n, arr, K);
}
int main() {
   vector<int> arr = {9, 2, 5, 3, 10}; int K = 3;
   cout << "Largest sum = " << getLargestSum(arr, K) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Largest sum = 22.3333