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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

设 dp[k][i] 表示前 i 个数分成 k 组的最大平均和。

预先计算前缀和，便于快速求区间平均。

枚举最后一组的起点进行转移。

复杂度分析：

时间复杂度：O(K * n^2)。

空间复杂度：O(K * n)。

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        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] - prefix[0]) / i;
        }

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

        return dp[k][n];
    }
}

func largestSumOfAverages(nums []int, k int) float64 {
	n := len(nums)
	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 := range dp {
		dp[i] = make([]float64, n+1)
	}

	for i := 1; i <= n; i++ {
		dp[1][i] = (prefix[i] - prefix[0]) / 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]
}

相似题目

题目	难度	考察点
410. 分割数组的最大值	困难	动态规划
1043. 分隔数组以得到最大和	中等	动态规划
813. 最大平均值和的分组	中等	动态规划
91. 解码方法	中等	动态规划
198. 打家劫舍	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/79044994