#813

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Largest Sum of Averages

Maximize the sum of averages by partitioning an integer array into at most k contiguous subarrays using dynamic programming.

array dynamic programming prefix sum

Problem Statement

Given an integer array nums and an integer k, partition nums into at most k non-empty contiguous subarrays. The score of a partition is defined as the sum of the averages of its subarrays, and every element of nums must be included in exactly one subarray.

Return the maximum sum of averages obtainable among all possible partitions. Answers within 10^-6 of the correct value are accepted. For example, nums = [9,1,2,3,9] with k = 3 can achieve a maximum score of 20.00000 by partitioning into [9], [1,2,3], [9].

Examples

Example 1

Input: nums = [9,1,2,3,9], k = 3

Output: 20.00000

The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20. We could have also partitioned nums into [9, 1], [2], [3, 9], for example. That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

Example 2

Input: nums = [1,2,3,4,5,6,7], k = 4

Output: 20.50000

Example details omitted.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 104
1 <= k <= nums.length

Solution Approach

Compute Prefix Sums

Calculate prefix sums of nums to quickly compute subarray sums, which allows O(1) average calculations during DP transitions.

Dynamic Programming State

Define dp[i][j] as the maximum sum of averages for the first i elements partitioned into j subarrays. Use the state transition dp[i][j] = max(dp[p][j-1] + average(p+1, i)) for all valid p < i.

Iterate and Update

Iterate through all i from 1 to n and j from 1 to k, updating dp[i][j] using all possible previous partition points p. The final result is dp[n][k].

Complexity Analysis

Metric	Value
Time	O(K * N^2)
Space	O(N)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Prefix Sum + Memoized Search

We can preprocess to obtain the prefix sum array $s$, which allows us to quickly get the sum of subarrays.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Solution 2: Dynamic Programming

We can transform the memoized search from Solution 1 into dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Continue Practicing

#689 maximum sum of 3 non overlapping subarrays #1000 minimum cost to merge stones #1140 stone game ii