FastPrepFastPrep
Problem Brief

Split Array Largest Sum

FULLTIMEOA

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.

Function Description

Complete the function splitArrayLargestSum in the editor.

splitArrayLargestSum has the following parameters:

  1. 1. int[] arr: an array of integers
  2. 2. int K: the number of pieces to split the array into

Returns

int: the minimum sum of the maximums of K sub-arrays

1Example 1

Input
arr = [1, 5, 3, 4, 2], K = 2
Output
6
Explanation
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

Limits and guarantees your solution can rely on.

  • 1 < K <= N < 300
  • 1 < arr[i] < 10^5
public int splitArrayLargestSum(int[] arr, int K) {
  // write your code here
}
Input

arr

[1, 5, 3, 4, 2]

K

2

Output

6

Sign in to submit your solution.