813. 最大平均值和的分组

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成最多 k 个相邻的非空子数组。分数由每个子数组内的平均值的总和构成。

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

返回我们所能得到的最大分数是多少。答案误差在 10-6 内被视为是正确的。

具体题目链接：
题目链接

思路

重点（这里下面的 j 表示的就是原题目中的 k，这里下面的 k 不是题目中的所示的 k（0 – i）），而是自己定义的一个变量。

状态表示（集合）dp[i][j]：以前i个数（也就是0-i，相当于以i下标结尾的数）分成j份的平均值的最大值。
状态计算：集合划分

找到最后一个不同点，将集合分成若干个子集

找到最后一个不同点（也就是最后一段的长度），将集合分成若干个子集（可以分成若干组长度j，题目已知）

划分标准，倒数第二段的终点，根据倒数第二段的终点在什么位置，最多是从0到i-1。
分类情况

1.枚举倒数第二段以k结尾（0 ~ i-1），先将0-k（k最多等于 i-1）分成j-1段

2.(第j段就是以i结尾的一段)这一部分的值是不变的，

因此如果想让整个j段的平均值之和最大，就让 j-1段的平均值之和最大即可

状态方程表示

dp[i][j] = dp[k][j-1] + presum[i] – presum[k] / i-k(最后一部分的平均值的最大值：使用前缀和技巧)

初始化：

创建dp数组，将长度+1；因为有j-1的情况

因为有j-1的情况所以枚举要从1开始，就需要将dp[0][0]进行初始化，

dp[0][0]分析：如果i长度为0的话，一个数都没有，平均值的最大值应该是0。即

dp[0][0] = 0；

代码

var largestSumOfAverages = function(nums, m) {
    let n = nums.length;
    let dp =  new Array(n+1).fill(-Infinity).map(() => Array(m+1).fill(-Infinity));
    let presum = new Array(n+1).fill(0);
    for(let i=1;i<=n;i++) {
        presum[i] = presum[i-1] + nums[i-1];
    }
    dp[0][0] = 0;

    for(let i=1;i<=n;i++) {
        for(let j=1;j<=m;j++) {
            for(let k = 0;k<i;k++) {
                let sum = (presum[i] - presum[k]) / Math.floor(i-k);
                dp[i][j] = Math.max(dp[i][j], dp[k][j-1] + sum);
            }
        }
    }
    return dp[n][m];
};
复制代码
复制代码

时间复杂度：状态维度 * 决策维度O(n * n * m)

空间复杂度：O(n * m)

总结

状态 dp(i,j)表示前 i个数字(以i为结尾)，分为 j组的最大平均值之和。其中 i的下标从 0 到 n，j的下标从 0 到 j。初始时，dp(i,k)全部为负无穷，只有 dp(0,0)为 0。转移时，对于 dp(i,j)，需要枚举上一次的分割位置(也就是倒数第二段) k，0<=k<i，找到 k使得 dp(j,k−1)+presum(i)−presum(k)/ i−k最大，并更新 f(i,k)。最终答案为 dp(n,m)。