0813. Largest Sum of Averages¶
题目信息¶
- 题号:
0813
- 难度:
Medium
- 主题:
数组、连续分组、平均值之和
- 原题:
- 重点:
必须按原顺序把数组划分为至多 k 个连续非空组,得分是各组平均值之和
题目重述¶
给定整数数组 nums 和整数 k。把数组按原有顺序划分为至多 k 个非空连续子数组,使每个元素恰好属于一个组。一次划分的得分等于所有组的算术平均值之和。
请返回能够取得的最大得分。不能重排元素,也不能把不连续的位置放入同一组。答案与真实值的误差在 10^-6 以内即可接受。
1 <= nums.length <= 100,1 <= nums[i] <= 10^4,1 <= k <= nums.length。
自建示例¶
最佳切分点靠近数组末尾:
输入:nums = [4,1,7,5], k = 2
输出:9.0
解释:划分为 [4,1,7] 和 [5] 时,得分为 4 + 5 = 9;其他至多两组的划分得分都不超过 9。
只允许使用一个分组:
输入:nums = [2,8,5], k = 1
输出:5.0
解释:k = 1 时不能切分数组,只能把全部元素作为一个连续组,得分为 (2 + 8 + 5) / 3 = 5。