#813
Largest Sum of Averages
specialist · 795 · lc medium +31 · verified · 54.9% accepted · 2,200 likes · top 48%
Description
You are given an integer array nums and an integer k. Divide the array into at most k non-empty contiguous subarrays. The score of a partition is the sum of the mean values of each subarray.
Every element of nums must belong to exactly one subarray, and the score is not required to be an integer.
Return the maximum achievable score over all valid partitions. Answers within 10-6 of the true answer are 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
Code
1
2
3