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