Description
You are given an integer array nums and an integer k. Partition the array into at most k non-empty adjacent subarrays. Return the largest sum of averages of the partitions.
Examples
Input:
nums = [9,1,2,3,9], k = 3Output:
20.00000Explanation:
[9], [1,2,3], [9] gives 20.
Input:
nums = [1,2,3,4,5], k = 2Output:
9.00000Explanation:
Partitioning [1,2,3,4,5] into 2 groups, the optimal split is [1,2,3] and [4,5] with averages 2.0 and 4.5, summing to 6.5. The split [1] and [2,3,4,5] gives 1.0+3.5=4.5. The split [1,2,3,4] and [5] gives 2.5+5.0=7.5. The maximum sum of averages across all valid partitions is 9.0.
Input:
nums = [7], k = 1Output:
7.00000Explanation:
With only one element and k=1, it is necessary to use the entire array as one partition. The average of [7] is 7.0, so the sum of averages is 7.0. This represents the edge case where there are the minimum possible array size.
Constraints
- •
1 ≤ nums.length ≤ 100 - •
1 ≤ nums[i] ≤ 10^4 - •
1 ≤ k ≤ nums.length