0813. Largest Sum of Averages

题目信息

题号:

0813

难度:

Medium

主题:

数组、连续分组、平均值之和

原题:

LeetCode 0813

重点:

必须按原顺序把数组划分为至多 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。