All problems

Split Array Largest Sum

Hard · binary search

You are given a list of non-negative integers nums and an integer k. Cut nums into exactly k non-empty parts, where each part is a run of neighbouring numbers and the parts together use every number, in their original order.

The score of a cut is the largest sum among its k parts. Return the smallest score over all the ways to cut nums into k parts.

Examples

Example 1

Input: nums = [3, 9, 4, 1, 6, 2], k = 3

Output: 12

Cut it as [3, 9], [4, 1, 6], [2]. The sums are 12, 11 and 2, so the score is 12, and no cut into three parts does better.

Example 2

Input: nums = [8, 1, 1, 8], k = 2

Output: 9

Cut it as [8, 1], [1, 8]. Both sums are 9.

Example 3

Input: nums = [6, 2, 4], k = 1

Output: 12

With one part, the part is the whole list.

Constraints