数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++数组最大平均和分区
问题陈述
给定一个数组，我们将一行数字A最多划分为K个相邻的（非空）组，则分数是每个组平均值的总和。可以获得的最大分数是多少？
示例
如果输入数组是{9, 2, 5, 3, 10}，则我们可以如下划分数组：
{9} {2, 5, 3} 和 {10}，则平均和为：
9 + (2 + 5 + 3)/ 3 + 10 = 22.33
算法
我们可以使用记忆化技术来解决这个问题：
- 令memo[i][k]为将A[i到n-1]最多划分为K部分的最佳分数
- 在第一组中，我们将A[i到n-1]划分为A[i到j-1]和A[j到n-1]，则我们的候选分区的分数为average(i, j) + score(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
更新于：2019年12月31日
浏览量：157
广告