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

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节
标签
数组 动态规划 前缀和

题目描述

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

image-20260928225048922

题意分析

把整个数组分成至多 k 个非空连续段，每个元素恰好属于一段，得分是各段平均值的和。分段不能改变原顺序，也不能遗漏元素，平均值和最终得分都可能不是整数。

本题所有元素都是正数。若把一段拆成两段，原平均值是两个新平均值的加权平均，不会超过其中较大的一个；两个正平均值之和则更大。因此还有可拆分的段时，增加一组会提高得分，最优解可以按恰好 k 组求出。

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

核心思路

[!blue]

定义 dp[g][i] 为前 i 个元素恰好分成 g 个非空连续段的最大得分。考虑最后一组从下标 j 开始：前 j 个元素必须分成 g-1 组，最后一组则固定为 nums[j..i-1]。

用 prefix[i] 保存前 i 个元素的和，最后一组的平均值为 (prefix[i]-prefix[j])/(i-j)，常数时间就能计算。枚举最后切点后，转移为：

dp[g][i] = max(dp[g-1][j] + (prefix[i]-prefix[j])/(i-j))，其中 g-1 <= j < i。

j >= g-1 保证前面有足够元素组成 g-1 个非空组，j < i 保证最后一组非空。最后一组确定后，前面部分必须取最优划分，否则替换成更优方案就能提高总分；遍历全部合法切点，又覆盖了所有可能的最后一组，因此转移既不会漏解，也不会取到非法划分。

解题步骤

  • 建立长度为 n+1 的浮点前缀和，令 prefix[0]=0。
  • 一组时不能切分，初始化 dp[1][i]=prefix[i]/i。
  • 组数 g 从 2 递增到 k，前缀长度 i 从 g 到 n，枚举 j 从 g-1 到 i-1 更新状态。所需的上一组数状态已经计算完毕。
  • 返回 dp[k][n]，表示全部元素恰好分成 k 组的最大得分。

未使用的状态虽然默认是 0，但循环只读取元素数足够的合法状态；本题得分为正，合法候选也一定能更新初值。k=1 时直接得到整个数组的平均值，k=n 时每个元素单独一组，得分等于总和。除法必须使用 double 或 float64，避免小数部分被截断。

代码实现

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(kn^2)$，共有 $O(kn)$ 个状态，每个状态最多枚举 $n$ 个最后切点。
  • 空间复杂度：$O(kn+n)$，分组表与前缀和。

关键点总结

[!green]

  • 状态按恰好组数定义，题目的正数条件保证用满允许组数最优。
  • i 和 j 表示前缀元素个数，最后一段为半开区间 [j,i)，长度是 i-j。
  • 每次只新增最后一组的平均值，前面的得分直接复用上一组数的最优状态。

易错点总结

[!yellow]

  • 切点取到 i 会出现空组与零除数。
  • 一组初值直接取最后元素，无法表示整个前缀。
  • 区间和端点减错，会把邻组元素重复计入。

相似题目

题目 难度 关联与区别
410. 分割数组的最大值 困难 同样选择连续分段，但本题最大化各段平均值之和，不能照搬最大段和的二分可行性。
1278. 分割回文串 III 困难 同样按前缀长度与段数做分割DP，每段代价不同，本题用前缀和计算平均值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/79044994
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！