class Solution {
public:
double largestSumOfAverages(vector<int>& nums, int k) {
}
};
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 <= 1001 <= nums[i] <= 1041 <= k <= nums.length原站题解
javascript 解法, 执行用时: 64 ms, 内存消耗: 41.5 MB, 提交时间: 2022-11-28 11:35:51
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var largestSumOfAverages = function(nums, k) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
dp[i] = prefix[i] / i;
}
for (let j = 2; j <= k; j++) {
for (let i = n; i >= j; i--) {
for (let x = j - 1; x < i; x++) {
dp[i] = Math.max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
}
}
}
return dp[n];
};
javascript 解法, 执行用时: 80 ms, 内存消耗: 43.4 MB, 提交时间: 2022-11-28 11:35:35
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var largestSumOfAverages = function(nums, k) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
const dp = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
for (let i = 1; i <= n; i++) {
dp[i][1] = prefix[i] / i;
}
for (let j = 2; j <= k; j++) {
for (let i = j; i <= n; i++) {
for (let 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];
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2022-11-28 11:35:12
func largestSumOfAverages(nums []int, k int) float64 {
n := len(nums)
prefix := make([]float64, n+1)
for i, x := range nums {
prefix[i+1] = prefix[i] + float64(x)
}
dp := make([][]float64, n+1)
for i := range dp {
dp[i] = make([]float64, k+1)
}
for i := 1; i <= n; i++ {
dp[i][1] = prefix[i] / float64(i)
}
for j := 2; j <= k; j++ {
for i := j; i <= n; i++ {
for x := j - 1; x < i; x++ {
dp[i][j] = math.Max(dp[i][j], dp[x][j-1]+(prefix[i]-prefix[x])/float64(i-x))
}
}
}
return dp[n][k]
}
golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-28 11:34:59
func largestSumOfAverages(nums []int, k int) float64 {
n := len(nums)
prefix := make([]float64, n+1)
for i, x := range nums {
prefix[i+1] = prefix[i] + float64(x)
}
dp := make([]float64, n+1)
for i := 1; i <= n; i++ {
dp[i] = prefix[i] / float64(i)
}
for j := 2; j <= k; j++ {
for i := n; i >= j; i-- {
for x := j - 1; x < i; x++ {
dp[i] = math.Max(dp[i], dp[x]+(prefix[i]-prefix[x])/float64(i-x))
}
}
}
return dp[n]
}
python3 解法, 执行用时: 196 ms, 内存消耗: 15 MB, 提交时间: 2022-11-28 11:34:36
'''
由于 dp[i][j] 的计算只利用到j−1 的数据，
因此也可以使用一维数组对 dp[i][j] 进行计算，
在计算过程中，要注意对 i 进行逆序遍历。
'''
class Solution:
def largestSumOfAverages(self, nums: List[int], k: int) -> float:
n = len(nums)
prefix = list(accumulate(nums, initial=0))
dp = [0.0] * (n + 1)
for i in range(1, n + 1):
dp[i] = prefix[i] / i
for j in range(2, k + 1):
for i in range(n, j - 1, -1):
for x in range(j - 1, i):
dp[i] = max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x))
return dp[n]
python3 解法, 执行用时: 224 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-28 11:33:18
'''
平均值和最大的分组的子数组数目必定是 k
为了方便计算子数组的平均值，我们使用一个数组 prefix 来保存数组 nums 的前缀和。
我们使用 dp[i][j] 表示 nums 在区间 [0,i−1] 被切分成 j 个子数组的最大平均值和，显然 i≥j，计算分两种情况讨论
1. 当 j=1 时，dp[i][j] 是对应区间 [0,i−1] 的平均值；
2. 当 j>1 时，我们将可以将区间 [0,i−1] 分成 [0,x−1] 和 [x,i−1] 两个部分，其中 x≥j−1，
那么 dp[i][j] 等于所有这些合法的切分方式的平均值和的最大值。
'''
class Solution:
def largestSumOfAverages(self, nums: List[int], k: int) -> float:
n = len(nums)
prefix = list(accumulate(nums, initial=0))
dp = [[0.0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][1] = prefix[i] / i
for j in range(2, k + 1):
for i in range(j, n + 1):
for x in range(j - 1, i):
dp[i][j] = max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x))
return dp[n][k]