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]，然后我们的候选分区的得分为平均值(i,j)+score（j，k-1）），其中平均值(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