Largest Sum of Averages
Medium · Dynamic Programming · Array · Dynamic Programming · Prefix Sum
Problem
You are given an integer array nums and an integer k. Split nums into at most k non-empty contiguous parts that together cover every element.
The score of a split is the sum of the averages of its parts. Return the highest score achievable. Answers within 10^-6 of the true value are accepted.
Examples
Input: nums = [4,1,7,2], k = 2 Output: 7.33333
Split as [4] | [1,7,2] for 4 + 10/3 = 7.33333. The other two-part splits score 7 and 6.
Input: nums = [6,6,6], k = 3 Output: 18.00000
Three single elements give 6 + 6 + 6 = 18.
Input: nums = [9,1,2,3,9], k = 1 Output: 4.80000
With one part the score is the average, 24 / 5 = 4.8.
Constraints
- 1 <= len(nums) <= 100
- 1 <= nums[i] <= 10^4
- 1 <= k <= len(nums)
Approaches
- Baseline: try every set of cuts — time O(2ⁿ · n), space O(1)
Follow-up
Since every value is positive, splitting a part never lowers the score: the average of a union is at most the larger average, which is at most the sum of both. So the best split always uses exactly k parts. Does that still hold if values can be negative?
Related problems
Start free on Cariara · Coding problems · System design studio
