C++での平均の最大の合計

数値Aの行を最大でK個の隣接するグループに分割するとし、スコアを各グループの平均の合計として設定します。達成できる最大のスコアを見つける必要があります。 A =[9,1,2,3,9]でKが3であるとすると、結果は20になります。これは、Aを[9]、[1、2、3]に分割することが最善の選択であるためです。 [9]。したがって、答えは9 +（1 + 2 + 3）/ 3 + 9 =20です。Aを[9、1]、[2]、[3、9]、

これを解決するには、次の手順に従います-

• 行列dpを定義する
• 再帰メソッドsolve（）を定義します。これには、配列A、インデックス、およびkが必要です。
• インデックス>=Aのサイズの場合、0を返します
• kが0の場合、-100000を返します
• dp [index、k]が– 1でない場合は、dp [index、k]を返します
• ret：=-infおよびsum：=0
• for i in range index to size of A – 1
  • 合計：=合計+ A [i]
  • ret：=retとsumの最大値/（i– index + 1）+ resolve（A、i + 1、k – 1）
• set dp [index、k]：=retandreturn。
• メインの方法から、次の手順を実行します-
• n：=Aのサイズ
• dp：=行列n x（K + 1）、–1で埋める
• returnsolve（A、0、K）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector < vector <double> > dp;
   double solve(vector <int>& A, int idx, int k){
      if(idx >= A.size()) return 0;
      if(!k) return -100000;
      if(dp[idx][k] != -1) return dp[idx][k];
      double ret = INT_MIN;
      double sum = 0;
      for(int i = idx; i < A.size(); i++){
         sum += A[i];
         ret = max(sum / (i - idx + 1) + solve(A, i + 1, k - 1), ret);
      }
      return dp[idx][k] = ret;
   }
   double largestSumOfAverages(vector<int>& A, int K) {
      int n = A.size();
      dp = vector < vector <double> > (n, vector <double>(K + 1, -1));
      return solve(A, 0, K);
   }
};
main(){
   vector<int> v = {9,1,2,3,9};
   Solution ob;
   cout << (ob.largestSumOfAverages(v, 3));
}

入力

[9,1,2,3,9]
3

出力

20