Largest Sum of Averages
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.
The partition must use every integer in nums, and the score is not necessarily an integer.
Return the maximum score you can achieve among all possible partitions. Answers within 10^-6 of the actual answer will be accepted.
Example 1
Input
nums = [9,1,2,3,9], k = 3Output
20The best choice is to partition
nums into [9], [1, 2, 3], and [9], giving a score of 9 + (1 + 2 + 3) / 3 + 9 = 20.Example 2
Input
nums = [1,2,3,4,5,6,7], k = 4Output
20.5The maximum achievable score for this array using at most 4 adjacent non-empty subarrays is
20.5.Constraints
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 10^4
- 1 <= k <= nums.length