Largest Sum of Averages: Partition DP with Prefix Sums

Largest Sum of Averages is LeetCode 813. You are given an integer array nums and an integer k. You partition the array into at most k non-empty adjacent (contiguous) groups. The score of a partition is the sum of the averages of each group. Return the maximum possible score.

Example: nums = [9, 1, 2, 3, 9], k = 3. The optimal partition is [9], [1, 2, 3], [9]. The averages are 9.0, 2.0, and 9.0, giving a total score of 20.0.

Why this problem matters

This problem is a clean example of partition DP, a pattern where you split an array into groups and optimize some objective across those groups. Unlike Split Array Largest Sum where you minimize the worst group, here you maximize the total of all group averages. The different objective changes the approach entirely: binary search on the answer does not apply here, but classic interval DP does.

The problem also teaches you how prefix sums can eliminate redundant work inside DP transitions. Computing the average of a subarray from scratch every time would add an extra O(n) factor. With prefix sums, each average computation drops to O(1), which is the difference between a solution that passes and one that times out.

If you have solved Coin Change or Partition Equal Subset Sum, you already know how to fill a DP table. This problem adds a new flavor: the state depends on both how many elements you have processed and how many groups you have used.

The DP approach with prefix sums

Define dp[i][j] as the maximum score you can get by partitioning the first i elements into exactly j groups.

Base case: dp[i][1] = average(nums[0..i-1]) for all i from 1 to n. With one group, you take everything as a single group and compute its average.

Transition: For j from 2 to k and i from j to n:

dp[i][j] = max over s from j-1 to i-1 of (dp[s][j-1] + average(nums[s..i-1]))

In words: try every possible split point s. The first s elements form j-1 groups (with score dp[s][j-1]), and elements from index s to i-1 form the last group (contributing its average).

Prefix sums make the average computation fast. Build a prefix sum array where prefix[i] = nums[0] + nums[1] + ... + nums[i-1]. Then average(nums[s..i-1]) = (prefix[i] - prefix[s]) / (i - s).

Answer: dp[n][k]. But since we want "at most k groups," we could also check dp[n][j] for all j from 1 to k. In practice, more groups never hurts (each group can be a single element with a potentially higher average), so dp[n][k] is always the answer.

def largest_sum_of_averages(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    dp = [[0.0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        dp[i][1] = prefix[i] / i

    for j in range(2, k + 1):
        for i in range(j, n + 1):
            for s in range(j - 1, i):
                avg = (prefix[i] - prefix[s]) / (i - s)
                dp[i][j] = max(dp[i][j], dp[s][j - 1] + avg)

    return dp[n][k]

Step-by-step walkthrough

Let's trace through nums = [9, 1, 2, 3, 9] with k = 3. The prefix sums are [0, 9, 10, 12, 15, 24].

The key pattern at every step is the same. To fill dp[i][j], you loop over all valid split points s and compute dp[s][j-1] + average(nums[s..i-1]). You keep the maximum. Prefix sums turn each average calculation into a single subtraction and division.

Complexity analysis

The three nested loops give O(n^2 * k). For LeetCode constraints (n up to 100 and k up to 100), that is at most 1,000,000 operations, well within time limits.

You can optimize space to O(n) by noticing that dp[i][j] only depends on dp[*][j-1], so you only need two rows at a time. But the 2D version is clearer and fast enough for the given constraints.

The building blocks

This problem is built on partition DP, where you decide where to place dividers in an array to optimize some objective.

The skeleton looks like this:

dp[i][j] = best score for first i elements using j groups
         = max/min over split point s of:
             dp[s][j-1] + cost(s, i)

This same building block appears in several other problems:

• Split Array Largest Sum (LeetCode 410): same partition structure, but you minimize the maximum group sum instead of maximizing the total of averages. That problem also admits a binary search solution.
• Palindrome Partitioning II (LeetCode 132): partition a string into the fewest palindrome substrings. The split-point loop is identical, but the cost function checks palindrome validity.
• Burst Balloons (LeetCode 312): another interval DP where you choose partition points, though the state definition is slightly different.

The use of prefix sums to speed up subarray computations is a second building block that shows up constantly. Any time you need the sum (or average) of a contiguous subarray inside a loop, prefix sums should be your first thought.

Edge cases to watch for

• k = 1: The entire array is one group. Return sum(nums) / len(nums).
• k >= len(nums): Every element is its own group. Return sum(nums) since the average of a single-element group is the element itself.
• Single element: nums = [5], k = 1. Return 5.0.
• All elements equal: nums = [3, 3, 3], k = 2. Any partition gives the same score of 3.0 + 3.0 = 6.0 (or similar depending on the split). Actually, splitting into more groups always gives the same result when all elements are equal.
• Floating point precision: The problem asks for a float answer. Python handles this naturally with float division. Just make sure you are using / and not //.

From understanding to recall

The partition DP template is one you will use over and over. Define a 2D state indexed by "how many elements" and "how many groups," then loop over split points. You can probably trace through the table right now.

But try writing it cold in a week. Was it dp[i][j] or dp[j][i]? Does s range from j-1 to i-1 or from 1 to i? Do you add the average of the last group or the first group? These details are where mistakes creep in during an interview.

Spaced repetition drills these details until the partition DP template is automatic. You write the three nested loops, the prefix sum setup, and the transition formula without pausing to think. That frees your mental energy for the parts of a problem that are actually new.

Related posts

• Split Array Largest Sum - Same partition DP skeleton but with a different objective (minimize the max group sum), and an elegant binary search alternative
• Partition Equal Subset Sum - A different kind of partition problem that reduces to 0/1 knapsack, showing how the same word "partition" can mean very different DP formulations
• Coin Change - Classic linear DP with a similar "try all options and pick the best" transition, but without the partition structure