Problem Brief
Efficient Cost
INTERNOA
See Snowflake online assessment and hiring insights
You will be given an integer array and a threshold value. The threshold represents the maximum length of subarrays that may be created for the challenge. Each subarray created has a cost equal to the maximum integer within the subarray. Partition the entire array into subarrays with lengths less than or equal to the threshold, and do it at a minimum cost. The subarrays are to be chosen from contiguous elements, and the given array must remain in its original order.
Function Description
Complete the function efficientCost in the editor.
efficientCost has the following parameters:
- 1.
int[] arr: an integer array - 2.
int threshold: the maximum length of subarrays
Returns
int: the minimum cost to partition the array
1Example 1
Input
arr = [1, 3, 4, 5, 2, 6], threshold = 3
Output
10
Explanation
Here are some ways to partition the arrays as an example. The lengths of partitions can differ as long as none are longer than threshold.
- Partition into 6 subarrays of length 1 as [1], [3], [4], [5], [2], [6]. The total cost is 1 + 3 + 4 + 5 + 2 + 6 = 21.
- Partition into 4 subarrays of various lengths: [1, 3], [4], [5], [2, 6]. The total cost is 3 + 4 + 5 + 6 = 18.
- Partition into 3 subarrays of length 2 as: [1, 3], [4, 5], [2, 6]. The total cost is 3 + 5 + 6 = 14
- Partition into 2 subarrays of length 3 as: [1, 3, 4], [5, 2, 6]. The total cost is 4 + 6 = 10.
The optimal cost is 10.
Constraints
Limits and guarantees your solution can rely on.
Unknown for now.