What is the main DP pattern used in Largest Sum of Averages?

State transition dynamic programming is the core pattern, where dp[i][j] represents the maximum sum of averages for first i elements with j subarrays.

Can prefix sums improve performance in this problem?

Yes, prefix sums allow O(1) computation of subarray averages, reducing the DP complexity from O(N^3) to O(K * N^2).

Is it necessary to use exactly k subarrays?

No, the problem allows at most k subarrays. Some partitions can use fewer subarrays if it leads to a higher sum of averages.

What is the acceptable error tolerance for answers?

Answers within 10^-6 of the correct value are considered valid due to floating-point computations.

What common mistakes should I avoid?

Avoid missing elements in partitions, incorrectly calculating averages without prefix sums, and mismanaging subarray indices in DP updates.

#813

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最大平均值和的分组

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成最多 k 个非空子数组，且数组内部是连续的。分数由每个子数组内的平均值的总和构成。注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。返回我们所能得到的最大分数是多少。答案误差在 10 …

数组动态规划前缀和

题目描述

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成最多 k 个非空子数组，且数组内部是连续的。分数由每个子数组内的平均值的总和构成。

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

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

示例 1:

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

示例 2:

输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000

提示:

1 <= nums.length <= 100
1 <= nums[i] <= 10⁴
1 <= k <= nums.length

lightbulb

解题思路

方法一：前缀和 + 记忆化搜索

我们可以先预处理得到前缀和数组 $s$ ，方便快速得到子数组的和。

接下来，我们设计一个函数 $\textit{dfs}(i, k)$ ，表示从数组下标 $i$ 开始，最多分成 $k$ 组的最大平均值和。答案为 $\textit{dfs}(0, k)$ 。

函数 $\textit{dfs}(i, k)$ 的执行逻辑如下：

当 $i = n$ 时，表示已经遍历到数组末尾，此时返回 $0$ 。

当 $k = 1$ 时，表示只剩下一组，此时返回从下标 $i$ 开始到数组末尾的平均值。

否则，我们在 $[i + 1, n)$ 的区间内枚举下一个分组的开始位置 $j$ ，计算从 $i$ 到 $j - 1$ 的平均值 $\frac{s[j] - s[i]}{j - i}$ ，加上 $\textit{dfs}(j, k - 1)$ 的结果，取所有结果的最大值。

时间复杂度 $O(n^2 \times k)$ ，空间复杂度 $O(n \times k)$ 。其中 $n$ 表示数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        @cache
        def dfs(i: int, k: int) -> float:
            if i == n:
                return 0
            if k == 1:
                return (s[n] - s[i]) / (n - i)
            ans = 0
            for j in range(i + 1, n):
                ans = max(ans, (s[j] - s[i]) / (j - i) + dfs(j, k - 1))
            return ans

        n = len(nums)
        s = list(accumulate(nums, initial=0))
        return dfs(0, k)

speed

复杂度分析

指标	值
时间	complexity is O(K * N^2) due to iterating over n elements and k partitions, checking all previous partition points. Space complexity is O(N) when using optimized 1D DP arrays.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Look for correct state definition for DP and clear handling of prefix sums.
question_mark
Check if candidate correctly updates dp using all partition points efficiently.
question_mark
Ensure floating-point precision is handled for averages and sum calculations.

warning

常见陷阱

外企场景

error
Forgetting to include all elements in exactly one subarray, violating the problem constraint.
error
Miscalculating averages without using prefix sums, causing O(N^3) performance.
error
Confusing indices for subarray boundaries during DP updates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit k to exactly a fixed number, forcing full use of all subarrays.
arrow_right_alt
Compute the largest sum of medians instead of averages, changing DP transitions.
arrow_right_alt
Allow only non-decreasing or non-increasing partitions, adding order constraints.

help

常见问题

外企场景

继续练习

#689 三个无重叠子数组的最大和 #1000 合并石头的最低成本 #1140 石子游戏 II