309. Split array - largest sum
Given an integer array a of size n and an integer k. Split the array a into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.
Example 1:
Input: a = [1, 2, 3, 4, 5], k = 3
Output:6
Explanation: There are many ways to split the array a[] into k consecutive subarrays. The best way to do this is to split the array a[] into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is only 6.
Example 2:
Input: a = [3,5,1], k = 3
Output: 5
Explanation: There is only one way to split the array a[] into 3 subarrays, i.e., [3], [5], and [1]. The largest sum among these subarrays is 5.
Now Your Turn!
Pick the correct output for the given inputInput: a = [1, 2, 3, 4, 5], k = 2
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 ≤ n ≤ 104
- 1 ≤ k ≤ n
- 1 ≤ a[i] ≤ 104