813.最大平均值和的分组

【LetMeFly】813.最大平均值和的分组

力扣题目链接:https://leetcode.cn/problems/largest-sum-of-averages/

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。

注意我们必须使用 nums 数组中的每一个数进行分组,并且分数不一定需要是整数。

返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。

 

示例 1:

输入: nums = [9,1,2,3,9], k = 3
输出: 20.00000
解释: 
nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20. 
我们也可以把 nums 分成[9, 1], [2], [3, 9]. 
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.

示例 2:

输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000

 

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 104
  • 1 <= k <= nums.length

方法一:DP + 前缀和

首先需要明白的是,虽然题目说的是“最多$k$组”,但其实等价于“分为$k$组”。因为能分成$k$组的话,绝对不分成$k-1$组。毕竟分组越少,除得越多。如果明白这个道理,下面的 证明 可以跳过。

证明:假设我们把数组分成了$k-1$组,那么我们可以将其中的某组一分为二(一定存在元素个数大于$1$的分组),这样,分母就会变小。(假设这组为$[a_1, a_2, \cdots, a_n, b]$,那么这组的平均数为$\frac{a_1+a_2+\cdots+a_n+b}{n+1}$,不失一般性,我们把其中的$b$分出来,这样平均数之和就变成了$\frac{a_1+a_2+\cdots+a_n}{n}+b>\frac{a_1+a_2+\cdots+a_n+b}{n+1}$

目的明确,确定分为$k$组。因此我们就可以使用数组$dp[n+1][k+1]$(其中$n$是数组中元素的个数),其中$dp[i][j]$代表将原始数组中的前$i$个元素分为$j$组的最大“平均数之和”

我们预处理求出一个前缀和数组$prefix[n+1]$,其中$prefix[i]$代表数组中前$i$个元素的和

  • 当$j=1$时,$dp[i][j] = dp[i][1] = prefix[i] / i$(前$i$个元素的平均数)
  • 否则,我们在$[j-1, i-1]$中挑选一个$l$,将$[0, i]$分为$[0, l-1]$和$[l,i-1]$两部分,因此$dp[i][j]=\max_{l\geq j-1}{dp[l][j-1]+\frac{\sum_{r=l}^{i-1}nums[r]}{i-l}}$

最终$dp[n][k]$即为答案

  • 时间复杂度$O(n^2\times k)$
  • 空间复杂度$O(n\times k)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
double largestSumOfAverages(vector<int>& nums, int k) {
int n = nums.size();
vector<double> prefix(n + 1);
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + nums[i - 1];
}
vector<vector<double>> dp(n + 1, vector<double>(k + 1));
for (int i = 1; i <= n; i++) {
dp[i][1] = prefix[i] / i;
}
for (int j = 2; j <= k; j++) {
for (int i = j; i <= n; i++) {
for (int l = j - 1; l < i; l++) {
dp[i][j] = max(dp[i][j], dp[l][j - 1] + (prefix[i] - prefix[l]) / (i - l));
}
}
}
return dp[n][k];
}
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/128087654


813.最大平均值和的分组
https://blog.letmefly.xyz/2022/11/28/LeetCode 0813.最大平均值和的分组/
作者
Tisfy
发布于
2022年11月28日
许可协议