数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
- 如果 index >= A 的大小，则返回 0
- 如果 k 为 0，则返回 -100000
- 如果 dp[index, k] 不为 – 1，则返回 dp[index, k]
- ret := -inf 且 sum := 0
- 对于 i 的范围从 index 到 A 的大小 – 1
- sum := sum + A[i]
- ret := ret 和 sum/(i – index + 1) + solve(A, i + 1, k – 1) 的最大值
- 设置 dp[index, k] := ret 并返回。
- 从主方法中，执行以下操作 -
- n := A 的大小
- dp := 一个 n x (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
更新于: 2020-05-04
105 次查看
广告