Split Array Largest Sum

The machine must split an array into m contiguous subarrays minimizing the largest subarray sum. Directly searching split points is exponential. The insight flips the problem: given a candidate cap X, greedy counting tells you the minimum number of segments needed if no segment may exceed X. That count is monotonic in X — larger caps need fewer segments — so binary search X between max(nums) and sum(nums).

def split_array(nums, m):
    def can(cap):
        segments = 1
        running = 0
        for num in nums:
            if running + num > cap:
                segments += 1
                running = num
            else:
                running += num
        return segments <= m
 
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Steps: (1) binary search the answer in [max(nums), sum(nums)], (2) for each candidate, greedily count segments — start a new segment whenever the running sum would exceed the cap, (3) if the count fits in m, try a smaller cap.

Time is O(n log(sum(nums))). Space is O(1).

Trickiest edge case: the lower bound. max(nums) is mandatory — a cap below the largest single element is impossible, since that element alone exceeds it. When m == n, every element is its own segment and the answer is the max element; the search converges there naturally.