Workspace

Problem workspace

3 day streakD

Split Array Largest Sum

HardBinary SearchSearch on the answer

The challenge

Split an array into exactly k nonempty contiguous parts, minimizing the largest part sum.

Nonempty nonnegative integer array. 1 ≤ k ≤ n; invalid k returns −1. Total sum fits signed 64-bit.

Example

[7, 2, 5, 10, 8], k = 2 → 18, using [7, 2, 5] and [10, 8].

Use the walkthrough below to inspect the input and each state change.

See Minimize the largest part, step by step

Inspect the comparison, the invariant, and the next boundary.

Answer-space searchk = 2
left10candidate—right32Search candidate values, not input indices
70215210384
Tested candidate / qualifying inputResolved positionParameters shown above
Left
10
Middle
—
Right
32
Step 01 / 6

Search the answer range

The candidate is a number, rather than an input index. Keep the smallest feasible value.

left = 10; right = 32

Recorded result so far

Not resolved
View exact input

Input: [7,2,5,10,8] · k = 2

Put it into code

For a candidate maximum sum, greedy packing uses the fewest parts. At most k parts is enough: nonnegative parts can be subdivided to reach exactly k.

Indices are zero-based. C++ uses C++17 or later.

def split_largest_sum(nums, k):
    # Nonempty nonnegative nums; exactly k nonempty parts.
    if k < 1 or k > len(nums):
        return -1
    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2
        parts, load = 1, 0
        for value in nums:
            if load + value > mid:
                parts += 1
                load = 0
            load += value
        if parts <= k:
            right = mid
        else:
            left = mid + 1
    return left

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap