Split the array into k non-empty contiguous parts. Minimize the largest sum among the parts.
DSA Animator › DSA Revision › Binary Search › Split Array Largest Sum
Remember: minimize the largest part sum by binary searching that sum. This same template solves shipping, books and painters. The video solves Split Array Largest Sum (LeetCode 410, Hard) with the Binary Search on Answer pattern from the Binary Search topic, and you can replay every step in the interactive Split Array Largest Sum animation.
Split the array into k non-empty contiguous parts. Minimize the largest sum among the parts.
For 7, 2, 5, 10, 8 with k equal to 2, the best split is 7, 2, 5 and 10, 8. The largest sum is 18.
Trying every way to place the cuts grows very fast. Dynamic programming works, but binary search is simpler and faster.
Guess a limit for the largest sum. Fill parts greedily, and count how many parts that limit needs. If it needs at most k parts, the limit works, so try smaller.
The range is 10, the biggest number, to 32, the total. Limit 21 works with 2 parts. 15 needs 3 parts, which is too many. 18 works, and 17 does not. So the answer is 18.
In code, low is the maximum and high is the sum. The check returns how many parts a limit needs. Move high to mid when it fits in k parts, otherwise move low past mid. It's O of n log of the sum.
Remember: minimize the largest part sum by binary searching that sum. This same template solves shipping, books and painters.