Split Array Largest Sum

Split an array into k nonempty continuous parts. Make the largest part sum as small as possible.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Split Array Largest Sum: Binary-search the first feasible capacity because the greedy number of contiguous parts never increases when capacity grows.

Input and goalSplit an array into `k` nonempty continuous parts. Make the largest part sum as small as possible.

Initialize answer boundsFor nums = [7,2,5,10,8] and k = 2, no limit below max(nums)=10 can hold 10, while sum(nums)=32 always fits in one part.

70215210384

boundslo = 10, hi = 32midpoint(10 + 32) // 2 = 21partitionnot tested yet

Recognize it

Use it when asked to minimize a numeric capacity or maximum load, and a candidate limit can be checked greedily with feasibility changing only once as the limit increases.

Keep true

Every limit below lo is infeasible, at least one feasible answer lies at or below hi, and parts_needed(limit) is nonincreasing; each midpoint decision preserves the smallest feasible limit inside [lo, hi].

Reuse it

For minimize-the-maximum problems, search the answer when a greedy capacity check is monotone: feasible moves the upper bound down, infeasible moves the lower bound above the candidate.

Pattern: Binary search on the answer.

Simple idea: Guess the largest allowed sum. Start a new part when adding the next value would pass the guess. If this needs at most k parts, the guess works.

def split_array_largest_sum(nums: list[int], parts: int) -> int:
   def parts_needed(limit: int) -> int:
      used = 1
      total = 0
      for num in nums:
         if total + num > limit:
            used += 1
            total = 0
         total += num
      return used

   left, right = max(nums), sum(nums)
   while left < right:
      middle = (left + right) // 2
      if parts_needed(middle) <= parts:
         right = middle
      else:
         left = middle + 1
   return left

Cost: $O(n\log s)$ time and $O(1)$ space, where $s$ is the sum range searched.