最大平均值和的分组

难度: Medium

给定数组 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] <= 10⁴
1 <= k <= nums.length

Submission

运行时间: 54 ms

内存: 16.1 MB

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        n = len(nums)
        pre = list(accumulate(nums, initial=0))
        f = [0.0] * (n + 1)
        for i in range(1, k + 1):
            for j in range(n - k + i, i - 1, -1):
                if i == 1:
                    f[j] = pre[j] / j
                else:
                    for l in range(i - 1, j):
                        x = f[l] + (pre[j] - pre[l]) / (j - l)
                        if x > f[j]:
                            f[j] = x
        return f[n]

Explain

这道题可以使用动态规划来解决。我们定义 f[i][j] 表示将前 i 个数分成 j 组所能得到的最大分数。我们可以枚举最后一组的起始位置 k，将问题转化为求 f[k][j-1] + avg(k+1, i) 的最大值，其中 avg(k+1, i) 表示第 k+1 个数到第 i 个数的平均值。为了避免重复计算前缀和，我们可以预处理前缀和数组 pre。最后的答案即为 f[n][k]。

时间复杂度: O(n^2*k)

空间复杂度: O(n)

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        n = len(nums)
        # 预处理前缀和数组
        pre = list(accumulate(nums, initial=0))
        # 定义状态数组 f，f[j] 表示将前 j 个数分成 i 组的最大分数
        f = [0.0] * (n + 1)
        # 枚举分组数 i
        for i in range(1, k + 1):
            # 枚举子数组的结束位置 j
            for j in range(n - k + i, i - 1, -1):
                # 如果只分一组，直接计算前 j 个数的平均值
                if i == 1:
                    f[j] = pre[j] / j
                else:
                    # 枚举子数组的起始位置 l
                    for l in range(i - 1, j):
                        # 转移方程：f[j] = max(f[j], f[l] + avg(l+1, j))
                        x = f[l] + (pre[j] - pre[l]) / (j - l)
                        if x > f[j]:
                            f[j] = x
        # 最终答案为 f[n]
        return f[n]

Explore

`f[i][j]` 在动态规划中的定义是将前 `i` 个数分成 `j` 组所能得到的最大分数。在代码中使用了一维数组 `f`，而非二维数组，是因为在计算过程中，每个状态 `f[j]` 只依赖于当前行的前一个状态（`f[l]`）和上一个分组数的状态。因此，可以通过从后向前更新 `f[j]` 来保证在更新 `f[j]` 时使用的是上一分组的数据，从而节省空间复杂度，将原本的二维数组压缩为一维数组。

在内层循环中，`j` 的循环起始于 `n-k+i` 是为了确保每个分组中至少有一个元素。由于总共有 `n` 个元素分成 `k` 组，最少每组一个元素，因此第 `i` 组的结束位置 `j` 至少需要保留足够的元素给剩余的 `k-i` 组。这样设计可以有效地减少不必要的循环迭代，避免计算那些不可能的状态，提高代码的运行效率。

在计算子数组的平均值时，如果不使用前缀和数组，则每次计算都需要遍历子数组来求和，这在多次计算时会导致大量的重复计算。通过使用前缀和数组 `pre`，可以快速计算任意子数组的和，即 `pre[j] - pre[i-1]` 表示从第 `i` 到第 `j` 的元素和。这样，计算平均值可以直接用 `(pre[j] - pre[i-1]) / (j - i + 1)` 实现，大大降低了时间复杂度。

当 `i == 1` 时，意味着只分成一组，这种情况下，整个数组本身就是一组，因此直接计算从第 1 个元素到第 `j` 个元素的总平均值即可，无需进行分组或使用更复杂的动态规划转移。这是基础情况，为后续分更多组做准备。在 `i > 1` 的情况下，需要考虑将数组分成多组，需要使用动态规划来寻找最优分组方案。