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