C ++中最大的平均值

假设我们将数字A的行划分为最多K个相邻的组，然后将score设置为每组平均值的总和。我们必须找到可以达到的最大分数。假设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

• 因为我的范围指数是A – 1

• 总和：=总和+ A [i]

• ret：= ret和sum /（（i – index +1）+ solve（A，i + 1，k – 1）的最大值

• 设置dp [index，k]：=退出并返回。

• 从主要方法中，执行以下操作-

• n：= A的大小

• dp：=矩阵nx（K + 1），用– 1填充

• 返回solve(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