友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
813. 最大平均值和的分组
给定数组 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
思路分析
完全没想到是动态规划！起初以为是贪心算法。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-07 22:21:16
*/
public double largestSumOfAverages(int[] nums, int k) {
int n = nums.length;
double[] prefix = new double[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
double[][] dp = new double[n + 1][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 x = j - 1; x < i; x++) {
dp[i][j] = Math.max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
}
}
}
return dp[n][k];
}