FastPrep
Problem · Dynamic Programming

Efficient Cost

Learn this problem
● MediumSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

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

efficientCost(arr: int[], threshold: int) → int

Complete the function efficientCost in the editor.

efficientCost has the following parameters:

  1. 1. int[] arr: an integer array
  2. 2. int threshold: the maximum length of subarrays

Returns

int: the minimum cost to partition the array

Examples

Example 1

arr = [1, 3, 4, 5, 2, 6]threshold = 3return = 10
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

Unknown for now.

More Snowflake problems

drafts saved locally
public int efficientCost(int[] arr, int threshold) {
    // write your code here
}
arr[1, 3, 4, 5, 2, 6]
threshold3
expected10
checking account