Problem · Dynamic Programming
Split Array Largest Sum
Given an array of integers arr and an integer K. While maintaining the order, split into exactly K pieces such the sum of maximum of every sub-array is minimum.
For example, given arr = [1, 5, 3, 4, 2] and K = 2, the output should be 6. Possible splits are: [[1], [5, 3, 4, 2]], [[1, 5], [3, 4, 2]], [[1, 5, 3], [4, 2]], [[1, 5, 3, 4], [2]]. The minimum sum of maximum would be [1], [5, 3, 4, 2] = 1 + 5 = 6.
Complete the function splitArrayLargestSum in the editor.
splitArrayLargestSum has the following parameters:
- 1.
int[] arr: an array of integers - 2.
int K: the number of pieces to split the array into
Returns
int: the minimum sum of the maximums of K sub-arrays
Examples
01 · Example 1
arr = [1, 5, 3, 4, 2] K = 2 return = 6
Possible splits are: [[1], [5, 3, 4, 2]], [1, 5], [3, 4, 2], [1, 5, 3], [4, 2], [1, 5, 3, 4], [2]]
The minimum sum of maximum would be = [1], [5, 3, 4, 2] = 1 + 5 = 6
Constraints
1 < K <= N < 3001 < arr[i] < 10^5
More LinkedIn problems
public int splitArrayLargestSum(int[] arr, int K) {
// write your code here
}
arr[1, 5, 3, 4, 2]
K2
expected6
sign in to submit