Introduction

This is the classic "minimize the largest partition sum" problem for contiguous partitions. For nonnegative integers, the standard efficient solution is binary search on the answer combined with a greedy feasibility check.

The optimization target is a number, not a split directly

Instead of guessing partition boundaries directly, think about a candidate maximum allowed partition sum X.

Then ask:

• can the array be split into at most k contiguous parts so that every part has sum at most X

That yes-or-no question is much easier to test than the full optimization problem.

Binary search the smallest feasible maximum sum

For nonnegative integers:

• the lower bound is max(nums) because every element must fit somewhere
• the upper bound is sum(nums) because one partition containing everything is always possible

Then binary search between those bounds.

Greedy feasibility check

Given a candidate limit X, scan left to right and start a new partition only when adding the next number would exceed X.

That greedy rule is correct for the feasibility test with nonnegative numbers:

1def can_split(nums, k, limit):
2    partitions = 1
3    current = 0
4
5    for num in nums:
6        if current + num > limit:
7            partitions += 1
8            current = num
9        else:
10            current += num
11
12    return partitions <= k

If this function returns True, then limit is feasible and you can try a smaller answer.

Full solution

1def minimize_largest_partition_sum(nums, k):
2    left = max(nums)
3    right = sum(nums)
4
5    while left < right:
6        mid = (left + right) // 2
7        if can_split(nums, k, mid):
8            right = mid
9        else:
10            left = mid + 1
11
12    return left
13
14
15nums = [7, 2, 5, 10, 8]
16print(minimize_largest_partition_sum(nums, 2))  # 18

For the example above, the best split is:

• '[7, 2, 5]'
• '[10, 8]'

The partition sums are 14 and 18, so the maximum is 18, which is optimal.

Why the greedy test works

For a fixed limit X, the greedy scan creates a new partition only when it has to. That means it uses as few partitions as possible under that limit. So if even the greedy approach needs more than k partitions, no other contiguous partitioning can do better for the same X.

That property is what makes binary search on the answer valid here.

This standard approach assumes nonnegative numbers

The usual binary-search-plus-greedy solution relies on nonnegative values. If negative numbers are allowed, the monotonic structure changes and the standard proof no longer applies cleanly.

So before using this solution blindly, confirm the input assumptions. In most interview and textbook versions of this problem, the array elements are nonnegative.

Complexity

If n is the number of elements and S is the search range between max(nums) and sum(nums), then:

• each feasibility check is O(n)
• binary search performs O(log S) checks

Overall complexity is:

• 'O(n log S)'

That is much better than trying every possible partition configuration.

Common Pitfalls

• Trying to enumerate all partition boundaries instead of binary-searching the answer.
• Forgetting that the standard greedy feasibility check assumes nonnegative numbers.
• Using exactly k partitions in the check when "at most k" is the correct feasibility condition.
• Setting the binary-search lower bound below max(nums).
• Mixing contiguous partition problems with unrelated subset-partition problems.

Summary

• For nonnegative arrays, the standard solution is binary search on the maximum allowed partition sum.
• A greedy left-to-right scan can test whether a candidate limit is feasible.
• The smallest feasible limit is the answer.
• The lower bound is max(nums) and the upper bound is sum(nums).
• This approach solves the contiguous version efficiently in O(n log S) time.