Largest Sum of Averages
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves exploring all possible ways to partition the array into k groups using recursion. For each state, defined by the current starting index and the number of partitions remaining, we try every possible split point for the next partition and recursively solve for the rest of the array. This method exhaustively checks every valid partition scheme.
Algorithm
- Define a recursive function, let's call it
solve(startIndex, partitionsLeft), which computes the maximum score for partitioning the subarraynums[startIndex:]intopartitionsLeftgroups. - Base Case 1: If
partitionsLeftis 1, we must group the entire remaining subarraynums[startIndex:]. The score is its average. Return this value. - Base Case 2: If
startIndexreaches the end of the array, we can't form any more non-empty partitions. Handle this boundary condition (e.g., return 0 ifpartitionsLeftis also 0, otherwise a very small number to signify an invalid path). - Recursive Step: Iterate through all possible end points
ifor the first partition, which would benums[startIndex...i]. The number of elements in the remaining subarray must be at leastpartitionsLeft - 1. - For each choice of
i, calculate the score asaverage(nums[startIndex...i]) + solve(i + 1, partitionsLeft - 1). - The function returns the maximum score found among all possible choices for
i. - The initial call to start the process is
solve(0, k). - To calculate averages efficiently, pre-compute a prefix sum array.
Walkthrough
The core idea is to define a function that solves the problem for a suffix of the array. Let's say solve(i, p) calculates the maximum score for partitioning nums[i:] into p groups.
To calculate solve(i, p), we can form the first group by taking nums[i...j] for any valid j. The score for this choice would be the average of nums[i...j] plus the result of recursively solving for the rest of the array, solve(j+1, p-1). We want to maximize this value over all possible j.
To avoid recomputing sums for averages repeatedly, we can use a prefix sum array. prefixSum[x] will store the sum of elements from nums[0] to nums[x-1]. The sum of nums[i...j] can then be found in O(1) time as prefixSum[j+1] - prefixSum[i].
This method is a direct translation of the problem's combinatorial nature but suffers from massive re-computation of the same subproblems, leading to exponential time complexity.
class Solution { private int[] nums; private int n; private double[] prefixSum; public double largestSumOfAverages(int[] nums, int k) { this.nums = nums; this.n = nums.length; this.prefixSum = new double[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } return solve(0, k); } private double solve(int startIndex, int partitionsLeft) { if (startIndex == n) { return 0; } if (partitionsLeft == 1) { return (prefixSum[n] - prefixSum[startIndex]) / (n - startIndex); } double maxScore = 0; for (int i = startIndex; i <= n - partitionsLeft; i++) { double currentAverage = (prefixSum[i + 1] - prefixSum[startIndex]) / (i - startIndex + 1); maxScore = Math.max(maxScore, currentAverage + solve(i + 1, partitionsLeft - 1)); } return maxScore; }}Complexity
Time
Exponential, roughly O(n^k). The number of ways to partition n items into k groups is C(n-1, k-1), which grows very quickly.
Space
O(n) or O(k) for the recursion call stack, whichever is larger. Given k <= n, it's O(n).
Trade-offs
Pros
Simple to conceive and directly models the problem statement.
Serves as a good foundation for more optimized dynamic programming solutions.
Cons
Extremely inefficient due to a large number of overlapping subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
This approach optimizes the brute-force recursion by using memoization, a top-down dynamic programming technique. We store the results of solved subproblems (identified by startIndex and partitionsLeft) in a cache or memoization table. When the same subproblem is encountered again, we retrieve the result from the cache instead of re-computing it, drastically reducing the number of calculations.
Algorithm
- Create a 2D memoization table,
memo[n][k+1], to store the results of subproblems. Initialize it with a value indicating that the state has not been computed (e.g., 0 or -1). - Use the same recursive function
solve(startIndex, partitionsLeft)as in the brute-force approach. - At the beginning of the function, check if
memo[startIndex][partitionsLeft]has already been computed. If so, return the stored value immediately. - If not, compute the result as before by iterating through all possible split points.
- Before returning the computed maximum score, store it in
memo[startIndex][partitionsLeft]. - Pre-computing prefix sums is still beneficial for O(1) average calculation.
Walkthrough
The recursive structure reveals a large number of overlapping subproblems. For example, solve(5, 2) might be called after partitioning [0...2] and [3...4], and also after partitioning [0...3] and [4...4]. Memoization avoids this redundant work.
We define a 2D array, memo[n][k+1], where memo[i][p] stores the result of solve(i, p). The function logic remains the same, but with an added check at the beginning to see if the result is already in our memo table. This turns the exponential complexity of the brute-force solution into a polynomial one.
class Solution { private int n; private double[] prefixSum; private double[][] memo; public double largestSumOfAverages(int[] nums, int k) { this.n = nums.length; this.prefixSum = new double[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } this.memo = new double[n][k + 1]; return solve(0, k); } private double solve(int startIndex, int partitionsLeft) { if (startIndex == n) { return 0; } if (partitionsLeft == 1) { return (prefixSum[n] - prefixSum[startIndex]) / (n - startIndex); } if (memo[startIndex][partitionsLeft] != 0) { return memo[startIndex][partitionsLeft]; } double maxScore = 0; for (int i = startIndex; i <= n - partitionsLeft; i++) { double currentAverage = (prefixSum[i + 1] - prefixSum[startIndex]) / (i - startIndex + 1); maxScore = Math.max(maxScore, currentAverage + solve(i + 1, partitionsLeft - 1)); } memo[startIndex][partitionsLeft] = maxScore; return maxScore; }}Complexity
Time
O(n² * k). There are `n * k` possible states for `(startIndex, partitionsLeft)`. Each state takes O(n) time to compute due to the loop for finding the split point.
Space
O(n * k) for the memoization table, plus O(n) for prefix sums and the recursion stack.
Trade-offs
Pros
Significantly more efficient than brute force and is fast enough to pass the given constraints.
Maintains a clear, logical structure that is easy to follow from the initial recursive idea.
Cons
The space complexity of O(n*k) might be a concern for larger constraints, though it's acceptable here.
Recursive solutions can sometimes lead to stack overflow errors for very deep recursion depths (not an issue for the given constraints).
This is a bottom-up, iterative dynamic programming solution. Instead of starting from the whole problem and breaking it down, we build the solution from the smallest subproblems up. We calculate the optimal scores for 1 partition, then use those results to find the optimal scores for 2 partitions, and so on, up to k partitions. This approach can be space-optimized.
Algorithm
- Create a prefix sum array
prefixof sizen+1. - Create a 1D DP array
dpof sizen+1.dp[i]will store the maximum score for partitioning the prefixnums[0...i-1]. - Handle the base case (1 partition): Initialize
dp[i]to be the average of the prefixnums[0...i-1]. This isprefix[i] / i. - Iterate for more partitions: Loop for the number of partitions
pfrom 2 tok.- Inside this loop, iterate through the prefix lengths
ifromndown top. - For each
i, iterate through possible split pointsjfromi-1down top-1. - The last group is
nums[j...i-1]. The previousp-1groups partitionnums[0...j-1]. The score for this isdp[j]. Note that since we iterateidownwards,dp[j]still holds the value from thep-1partitions step. - Update
dp[i]with the maximum value found:dp[i] = max(dp[i], dp[j] + average(nums[j...i-1])).
- Inside this loop, iterate through the prefix lengths
- After all loops complete,
dp[n]will hold the maximum score for partitioning the entire arraynumsintokgroups.
Walkthrough
We can define our DP state dp[i][p] as the largest sum of averages for partitioning the prefix nums[0...i-1] into p groups. The recurrence relation is:
dp[i][p] = max_{p-1 <= j < i} (dp[j][p-1] + average(nums[j...i-1]))
This would require an O(n*k) DP table. However, we can observe that to compute the values for p partitions, we only need the results from p-1 partitions. This allows for a space optimization. We can use a single 1D array, dp[n+1], where dp[i] stores the max score for partitioning nums[0...i-1] into the current number of partitions being considered.
We first fill the dp array for p=1. Then, for each subsequent p from 2 to k, we update the dp array. To use a single array, we must iterate the prefix length i from n down to p. This ensures that when we calculate dp[i] (for p partitions), the values dp[j] (where j < i) we access are still from the previous iteration (p-1 partitions).
class Solution { public double largestSumOfAverages(int[] nums, int k) { int n = nums.length; double[] prefixSum = new double[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } double[] dp = new double[n + 1]; // Base case: p = 1 partition for (int i = 1; i <= n; i++) { dp[i] = prefixSum[i] / i; } // Iterate for p = 2 to k partitions for (int p = 2; p <= k; p++) { // Iterate backwards for prefix length i for (int i = n; i >= p; i--) { // Iterate through split points j for (int j = i - 1; j >= p - 1; j--) { double lastGroupAverage = (prefixSum[i] - prefixSum[j]) / (i - j); dp[i] = Math.max(dp[i], dp[j] + lastGroupAverage); } } } return dp[n]; }}Complexity
Time
O(n² * k). The three nested loops for `p`, `i`, and `j` dominate the runtime.
Space
O(n). We use a 1D array `dp` of size `n+1` and a prefix sum array of size `n+1`.
Trade-offs
Pros
Most efficient approach in terms of space complexity.
Avoids recursion overhead, which can lead to slightly better performance in practice.
Guaranteed not to have stack overflow issues.
Cons
The logic, especially the nested loops and state transitions, can be less intuitive to grasp compared to the recursive top-down approach.
Solutions
Solution
class Solution {private Double[][] f;private int[] s;private int n;public double largestSumOfAverages(int[] nums, int k) { n = nums.length; s = new int[n + 1]; f = new Double[n + 1][k + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } return dfs(0, k); }private double dfs(int i, int k) { if (i == n) { return 0; } if (k == 1) { return (s[n] - s[i]) * 1.0 / (n - i); } if (f[i][k] != null) { return f[i][k]; } double ans = 0; for (int j = i; j < n; ++j) { double t = (s[j + 1] - s[i]) * 1.0 / (j - i + 1) + dfs(j + 1, k - 1); ans = Math.max(ans, t); } return f[i][k] = ans; }}class Solution {public: double largestSumOfAverages(vector<int> &nums, int k) { int n = nums.size(); int s[n + 1]; double f[n][k + 1]; s[0] = 0; memset(f, 0, sizeof f); for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i]; function<double(int, int)> dfs = [&](int i, int k) -> double { if (i == n) return 0; if (k == 1) return (s[n] - s[i]) * 1.0 / (n - i); if (f[i][k]) return f[i][k]; double ans = 0; for (int j = i; j < n; ++j) { double t = (s[j + 1] - s[i]) * 1.0 / (j - i + 1) + dfs(j + 1, k - 1); ans = max(ans, t); } return f[i][k] = ans; }; return dfs(0, k); }};class Solution: def largestSumOfAverages(self, nums: List[int], k: int) -> float: @ cache def dfs(i, k): if i == n: return 0 if k == 1: return (s[- 1] - s[i]) / (n - i) ans = 0 for j in range(i, n): t = (s[j + 1] - s[i]) / (j - i + 1) + dfs(j + 1, k - 1) ans = max(ans, t) return ans n = len(nums) s = list(accumulate(nums, initial=0)) return dfs(0, k)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.