LeetCode 813. 最大平均值和的分组

2025-03-06 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 813. 最大平均值和的分组

题意分析

给一个非负整数数组和上限 k，要把它切成至多 k 个连续且非空的子数组，让「每组的平均数之和」最大。

「连续」是最强的约束信号：不能重排、不能跳着挑元素，能做的只是在相邻元素之间选若干个切点。

「至多 k 组」看似要在 1 到 k 之间再枚举一层，但元素非负时多切一刀不会变差 —— 把一组拆成两半，两个平均数之和不小于两者中较大的那个，而后者又不小于原来的加权平均。所以直接按「恰好 min(k, n) 组」计算即可。

约束很宽松：n 最多 100、k 不超过 n、元素在 $[0, 10^4]$，即使三重循环也只有 $10^6$ 量级。答案是浮点数，允许 $10^{-5}$ 的误差，但中间运算必须走浮点，不能用整除。

解法：前缀和 + 分组动态规划

核心思路

暴力做法是枚举所有切点组合，从 n - 1 个空隙里选 k - 1 个，方案数是 $\binom{n-1}{k-1}$，n = 100 时是天文数字。

瓶颈在于大量方案共享同一个前缀结构：「前 j 个元素切成 g 组的最优值」会在指数级的方案里被反复重算。

关键观察是最优子结构：无论前面怎么切，最后一组一定是某个后缀 nums[j .. i-1]，它对答案的贡献 (prefix[i] - prefix[j]) / (i - j) 只由 j 和 i 决定，与前面的切法完全无关；而前面那部分只需要取「前 j 个元素切成 g - 1 组的最大值」。两段互不干扰，可以分别取最优。

于是定义状态：dp[g][i] 表示把前 i 个元素恰好切成 g 个非空连续组时，各组平均数之和的最大值。转移是 dp[g][i] = max{ dp[g-1][j] + (prefix[i] - prefix[j]) / (i - j) }，j 取遍 [g-1, i-1]；下界 g-1 保证前面那 g - 1 组每组至少一个元素。边界是 dp[1][i] = prefix[i] / i，即前 i 个元素独占一组。答案是 dp[k][n]。

解题步骤

先做 k = min(k, n)。k 大于 n 时根本切不出这么多非空组，不修正的话最终读到的 dp[k][n] 是从未被写过的初值。

预处理前缀和 prefix，其中 prefix[t] 是前 t 个元素之和。有了它，任意区间 [j, i-1] 的和是 prefix[i] - prefix[j]，把转移里的求和从 $O(n)$ 降到 $O(1)$。prefix 直接用 double 存，从源头上避免整数除法。

初始化 dp[1][i] = prefix[i] / i。这是唯一不依赖其他状态的一层，必须先填好，否则整个递推没有起点。

外层枚举组数 group 从 2 到 k，中层枚举前缀长度 i 从 group 到 n。i 从 group 起步是因为不足 group 个元素凑不出 group 个非空组，这些状态不可达也不该参与转移。

内层枚举上一段的结束位置 j 从 group - 1 到 i - 1，用 dp[group-1][j] + (prefix[i] - prefix[j]) / (i - j) 更新最大值。j 的上界取 i - 1 而非 i，保证最后一组至少含一个元素，否则除数为 0。

返回 dp[k][n]。

以 nums = [9, 1, 2, 3, 9]、k = 3 走一遍（n = 5，prefix = [0, 9, 10, 12, 15, 24]）：

第一层：dp[1][1] = 9，dp[1][2] = 10 / 2 = 5，dp[1][3] = 12 / 3 = 4，dp[1][4] = 15 / 4 = 3.75，dp[1][5] = 24 / 5 = 4.8。

第二层 group = 2。dp[2][2] 只有 j = 1 一个选择：9 + (10 - 9) / 1 = 10。dp[2][3] 取 j = 1 的 9 + 3 / 2 = 10.5 与 j = 2 的 5 + 2 / 1 = 7，得 10.5。dp[2][4] 取 j = 1 的 9 + 6 / 3 = 11、j = 2 的 5 + 5 / 2 = 7.5、j = 3 的 4 + 3 / 1 = 7，得 11。dp[2][5] 取 j = 1 的 9 + 15 / 4 = 12.75、j = 2 的 5 + 14 / 3 \approx 9.67、j = 3 的 4 + 12 / 2 = 10、j = 4 的 3.75 + 9 / 1 = 12.75，得 12.75。

第三层 group = 3，只需要 dp[3][5]：j = 2 给出 10 + 14 / 3 \approx 14.67，j = 3 给出 10.5 + 12 / 2 = 16.5，j = 4 给出 11 + 9 / 1 = 20。取最大得 20。

返回 20。回溯这条路径：j = 4 说明最后一组是 [9]，而 dp[2][4] = 11 来自 j = 1，说明前面切成 [9] 和 [1, 2, 3]。完整方案是 [9] [1,2,3] [9]，平均数之和为 $9 + 2 + 9 = 20$，与递推结果一致。

代码实现

class Solution {
    // 只要能快速算出任意区间平均值，动态规划就能转成标准的状态转移问题。
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        k = Math.min(k, n);

        double[] prefix = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        double[][] dp = new double[k + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            dp[1][i] = prefix[i] / i;
        }

        for (int group = 2; group <= k; group++) {
            for (int i = group; i <= n; i++) {
                for (int j = group - 1; j < i; j++) {
                    double avg = (prefix[i] - prefix[j]) / (i - j);
                    dp[group][i] = Math.max(dp[group][i], dp[group - 1][j] + avg);
                }
            }
        }

        return dp[k][n];
    }
}

func largestSumOfAverages(nums []int, k int) float64 {
    // 只要能快速算出任意区间平均值，动态规划就能转成标准的状态转移问题。
    n := len(nums)
    if k > n {
        k = n
    }

    prefix := make([]float64, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + float64(nums[i])
    }

    dp := make([][]float64, k+1)
    for i := 0; i <= k; i++ {
        dp[i] = make([]float64, n+1)
    }

    for i := 1; i <= n; i++ {
        dp[1][i] = prefix[i] / float64(i)
    }

    for group := 2; group <= k; group++ {
        for i := group; i <= n; i++ {
            for j := group - 1; j < i; j++ {
                avg := (prefix[i] - prefix[j]) / float64(i-j)
                val := dp[group-1][j] + avg
                if val > dp[group][i] {
                    dp[group][i] = val
                }
            }
        }
    }

    return dp[k][n]
}

复杂度分析

时间复杂度：$O(k \cdot n^2)$，状态数是 $k \times n$，每个状态要枚举上一段的结束位置，即 $O(n)$ 次转移；前缀和让每次转移里的区间求和降到常数。

空间复杂度：$O(kn)$，二维 dp 表按组数与前缀长度各开一维。由于 dp[group] 只依赖 dp[group-1]，用两行滚动即可压到 $O(n)$。

关键点总结

「连续分段求最优」几乎必然对应「枚举最后一段的起点」这一转移形态。认准最后一段是某个后缀之后，状态定义和转移方程基本是被逼出来的。

状态定义里的「恰好」还是「至多」要一开始就钉死。本题因为元素非负、多切不亏，才敢把「至多 k 组」直接当成「恰好 min(k, n) 组」；这个前提说不出来，边界处理就是碰运气。

前缀和是分段 dp 的标配。它把「求某段的和」从 $O(n)$ 降到 $O(1)$，正好抵消枚举切点多出来的那一层循环。

循环下界承担着「排除不可达状态」的职责。i 从 group 起、j 从 group - 1 起，都是在保证每组非空，随手写成从 1 开始就等于默许空组存在。

面试视角：写完 $O(kn^2)$ 后主动提一句「dp[group] 只依赖上一行，可以滚动到 $O(n)$ 空间」，是成本极低的加分点；再顺手说明「本题 $n \le 100$，不优化也够」，能体现你在权衡而不是背优化。

面试视角：这题最容易被追问的是「如果元素可以为负呢」。答案是「至多 k 组」不再等价于「恰好 k 组」，需要在所有 dp[g][n]（g 从 1 到 k）里取最大值。能答上这一问，说明你真的想过前提而不是套模板。

易错点总结

错误写法：不做 k = min(k, n)。用 nums = [1, 2]、k = 5 试：dp[5][2] 这个状态永远进不了循环体，保持初值 0，函数返回 0 而正确答案是 3。

错误写法：把 dp[1][i] 初始化成 nums[i - 1] 而不是 prefix[i] / i。用 nums = [4, 2]、k = 1 试：dp[1][2] 应是 (4 + 2) / 2 = 3，写成 nums[1] = 2 后直接返回 2。

错误写法：区间平均用整数除法。用 nums = [9, 1, 2, 3, 9]、k = 3 试：(24 - 10) / 3 在整型下截断成 4 而不是 4.6667，误差沿着转移层层放大，最终答案对不上。前缀和数组要直接用 double，或在除法处显式转型。

错误写法：以为「组数越少平均和越大」而直接返回 dp[1][n]。同一组用例里整体平均只有 4.8，而 [9] [1,2,3] [9] 能拿到 20，差了四倍。

错误写法：滚动优化时只留一维 dp[i] 并按 i 递增原地更新。dp[j]（j < i）在本轮已经被刷成第 group 层的值，转移读到的不再是 group - 1 层，等价于允许总组数超过 k，结果偏大。滚动必须按 i 倒序，或者老实用两行。

错误写法：区间和写成 prefix[i] - prefix[j - 1]。本题约定 prefix[t] 是前 t 个元素之和，[j, i-1] 的和只能是 prefix[i] - prefix[j]，端点错位一格会把邻组的元素算进当前组的平均数里。

错误写法：内层 j 的上界写成 i 而不是 i - 1，允许最后一组为空。除数 i - j 变成 0，分子也是 0，double 下 0.0 / 0 得到 NaN，而 Math.max 一旦碰上 NaN 就会把它传播下去，最终返回 NaN。

错误写法：为了保险，在返回时把 dp[1][n] 到 dp[k][n] 全部取一遍最大值。本题结果不会变错，但这说明没意识到「元素非负时多分一组不会更差」这个前提；一旦面试官把值域改成可负，这层遮掩就会暴露成真正的漏洞。

相似题目

题目	难度	考察点
132. 分割回文串 II	困难	同为连续分段 dp，段的代价换成「是否回文」
312. 戳气球	困难	区间 dp，决策是最后戳哪个而非在哪里下刀
410. 分割数组的最大值	困难	目标是最小化最大段和，可改用二分答案
644. 子数组最大平均数 II	困难	同样围绕平均数，但用二分答案配前缀和判定
698. 划分为k个相等的子集	中等	分组不要求连续，退化成带剪枝的搜索