Binary Search Searching the answer
243. Split Array Largest Sum
You are given an array nums of non-negative integers and an integer k. Cut nums into exactly k
parts. Each part is a non-empty subarray, every element belongs to exactly one part, and the elements keep
their order. A subarray is a run of elements that sit next to each other in nums.
Each part has a sum: the sum of its elements. The largest of the k sums is the split's largest part sum.
Return the smallest largest part sum that any split into k parts can have.
Example 1
Input: nums = [8, 3, 5, 9, 2, 6, 4], k = 3
14Explanation: Cut the array into [8, 3], [5, 9] and [2, 6, 4]. The part sums are 11, 14 and 12, so the largest is
14. Every other split into three parts has a part that adds up to more than 14.
Example 2
Input: nums = [7, 1, 1, 1, 1, 1, 1, 1], k = 2
7Explanation: [7] and the seven 1s both add up to 7. No split can do better, because the 7 belongs to some part, and
that part adds up to at least 7.
Example 3
Input: nums = [0, 5, 0, 5, 0], k = 4
5Explanation: One best split is [0], [5], [0] and [5, 0]. A part may add up to 0. Each 5 belongs to some part,
so the answer cannot be below 5.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1050 ≤ nums[i] ≤ 1091 ≤ k ≤ nums.length
Clarifying questions
What you would ask an interviewer before writing any code.