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
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 = 32Recorded 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#include <algorithm>
#include <numeric>
#include <vector>
long long split_largest_sum(const std::vector<int>& nums, int k) {
if (k < 1 || k > static_cast<int>(nums.size())) return -1;
long long left = *std::max_element(nums.begin(), nums.end());
long long right = std::accumulate(nums.begin(), nums.end(), 0LL);
while (left < right) {
long long mid = left + (right - left) / 2, load = 0;
int parts = 1;
for (int value : nums) {
if (load + value > mid) { ++parts; load = 0; }
load += value;
}
if (parts <= k) right = mid;
else left = mid + 1;
}
return left;
}