题目描述

我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

样例

输入：
A = [9,1,2,3,9]
K = 3
输出：20
解释：
A 的最优分组是[9]、[1, 2, 3]、[9]。得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20。
我们也可以把 A 分成 [9, 1]、[2]、[3, 9]。
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值。

提示

• 1 <= A.length <= 100
• 1 <= A[i] <= 10000
• 1 <= K <= A.length
• 答案误差在 10^-6 内被视为是正确的。

算法

(动态规划) $O(n^2K)$

1. 状态 $f(i, k)$ 表示前 $i$ 个数字，分为 $k$ 组的最大平均值之和。其中 $i$ 的下标从 0 到 $n$，$k$ 的下标从 0 到 $K$。
2. 初始时，$f(i, k)$ 全部为负无穷，只有 $f(0, 0)$ 为 0。
3. 转移时，对于 $f(i, k)$，需要枚举上一次的分割位置 $j$，$0 <= j < i$，找到 $j$ 使得 $f(j, k - 1) + \frac{sum(i) - sum(j)}{i - j}$ 最大，并更新 $f(i, k)$。
4. 最终答案为 $f(n, K)$。

时间复杂度

• $sum$ 前缀和数组可以预处理。
• 状态数为 $O(nK)$ 个，每次转移需要 $O(n)$ 的时间枚举，故时间复杂度为 $O(n^2K)$。

空间复杂度

• 需要 $O(nK)$ 的空间记录状态。

C++ 代码

class Solution {
public:
    double largestSumOfAverages(vector<int>& A, int K) {
        int n = A.size();
        vector<int> sum(n + 1, 0);
        vector<vector<double>> f(n + 1, vector<double>(K + 1, -1e7));

        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + A[i - 1];

        f[0][0] = 0;

        for (int i = 1; i <= n; i++)
            for (int k = 1; k <= min(K, i); k++)
                for (int j = 0; j < i; j++)
                    f[i][k] = max(f[i][k], f[j][k - 1] + 1.0 * (sum[i] - sum[j]) / (i - j));

        return f[n][K];
    }
};