Watch 10 video solutions for Largest Sum of Averages, a medium level problem involving Array, Dynamic Programming, Prefix Sum. This walkthrough by Hua Hua has 6,648 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthProblem 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 | 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. |