Largest Sum of Averages - Solution & Explanation
Problem Statement
You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.
Note that the partition must use every integer in nums, and that the score is not necessarily an integer.
Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.
Example 1:
Input: nums = [9,1,2,3,9], k = 3 Output: 20.00000 Explanation: 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
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1041 <= k <= nums.length
Approach Overview
Problem Overview: You are given an array nums and an integer k. Split the array into at most k non‑empty contiguous groups. The score is the sum of the average of each group. Your goal is to choose the partition that maximizes this total score.
Approach 1: Dynamic Programming with Prefix Sums (Time: O(n^2 * k), Space: O(n * k))
The core observation: once you fix the last partition boundary, the remaining prefix becomes a smaller subproblem. Precompute prefix sums so any subarray average avg(i..j) can be calculated in O(1). Let dp[i][g] represent the maximum score you can get using the first i elements split into g groups. For each state, iterate over the last cut position j where the final group starts, and combine dp[j][g-1] with the average of nums[j..i-1]. Prefix sums remove repeated summations, keeping transitions efficient. This approach is the standard solution when combining dynamic programming with fast range averages via prefix sums.
Approach 2: Recursive with Memoization (Time: O(n^2 * k), Space: O(n * k))
Instead of filling a table iteratively, you can define a recursive function dfs(i, g) that returns the maximum score obtainable starting at index i with g groups remaining. The function tries every possible ending position for the current group, computes the average using prefix sums, and recurses on the rest of the array. Memoization stores results for each (i, g) pair to avoid recomputation. Each state explores up to n split points, leading to the same O(n^2 * k) time complexity as the bottom‑up DP. This version often feels more intuitive when reasoning about partition decisions in array problems.
Recommended for interviews: The dynamic programming with prefix sums approach is what most interviewers expect. Start by explaining the brute idea of trying all partition points, then show how DP reuses subproblem results and prefix sums reduce average computation to O(1). That progression demonstrates both problem decomposition and optimization skills.
Approach 1: Approach 1: Dynamic Programming with Prefix Sums
This approach utilizes dynamic programming combined with prefix sums to efficiently calculate the sum of subarray averages when partitioned optimally. The prefix sum array allows for quick computation of subarray sums, and dynamic programming is used to build the optimal solution up to k partitions.
First, compute prefix sums for the array, then utilize dynamic programming to calculate the maximum sum of averages for each possible partition using the prefix sums. The dp array stores the maximum score achievable for each subarray starting at index i using up to m partitions.
Complexity
Time Complexity: O(n^2 * k), where n is the length of the array, and k is the number of partitions.
Space Complexity: O(n * k) due to the dp table.
Approach 2: Approach 2: Recursive with Memoization
This approach uses recursion with memoization to solve for the maximum sum of averages by exploring all possible partition strategies and storing computed results for reuse. This avoids redundant computations and optimizes performance compared to plain recursion.
This C implementation defines a solve function that handles partitioning recursively, memoizing previously calculated scores to prevent redundant computation. This function checks scores for partitions from index i with m partitions left.
Complexity
Time Complexity: O(n^2 * k) as each subproblem is solved once.
Space Complexity: O(n * k) for memoization table.
Approach 3: Prefix Sum + Memoized Search
We can preprocess to obtain the prefix sum array s, which allows us to quickly get the sum of subarrays.
Next, we design a function dfs(i, k), which represents the maximum sum of averages when dividing the array starting from index i into at most k groups. The answer is dfs(0, k).
The execution logic of the function dfs(i, k) is as follows:
- When
i = n, it means we have traversed to the end of the array, and we return0. - When
k = 1, it means there is only one group left, and we return the average value from indexito the end of the array. - Otherwise, we enumerate the starting position
jof the next group in the interval[i + 1, n), calculate the average value fromitoj - 1as\frac{s[j] - s[i]}{j - i}, add the result ofdfs(j, k - 1), and take the maximum value of all results.
The time complexity is O(n^2 times k), and the space complexity is O(n times k). Here, n represents the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Dynamic Programming
We can transform the memoized search from Solution 1 into dynamic programming.
Define f[i][j] to represent the maximum sum of averages when dividing the first i elements of the array nums into at most j groups. The answer is f[n][k].
For f[i][j], we can enumerate the end position h of the previous group, calculate f[h][j-1], add the result of \frac{s[i] - s[h]}{i - h}, and take the maximum value of all results.
The time complexity is O(n^2 times k), and the space complexity is O(n times k). Here, n represents the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with Prefix Sums | Time Complexity: O(n^2 * k), where n is the length of the array, and k is the number of partitions. |
| Approach 2: Recursive with Memoization | Time Complexity: O(n^2 * k) as each subproblem is solved once. |
| Prefix Sum + Memoized Search | — |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sums | O(n^2 * k) | O(n * k) | Standard optimized solution. Best for interviews and large inputs where repeated average calculations must be avoided. |
| Recursive with Memoization | O(n^2 * k) | O(n * k) | Useful when reasoning about partitions recursively. Easier to implement if you prefer top‑down DP. |
Video Solution
花花酱 LeetCode 813. Largest Sum of Averages - 刷题找工作 EP179 • Hua Hua • 6,665 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest Sum of Averages easy or hard?
How to solve Largest Sum of Averages in O(n^2 * k)?
What is the best approach for Largest Sum of Averages?
What data structure is used in Largest Sum of Averages?
What is the time complexity of Largest Sum of Averages?
Largest Sum of Averages Python or Java solution approach?
Is Largest Sum of Averages asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Largest Sum of Averages with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor