DSA Split Array Largest Sum

The problem

Split Array Largest Sum asks for a split of an array into at most k parts that makes the largest part sum as small as possible. The parts are contiguous and keep the original order. Every part is non-empty.

Making one part smaller forces another part to grow. The best split balances that trade-off. The cases below are the ones this article solves.

cases = [
    ([7, 2, 5, 10, 8], 1, 32),
    ([7, 2, 5, 10, 8], 2, 18),
    ([7, 2, 5, 10, 8], 3, 14),
    ([10, 2, 2, 4, 5, 2], 3, 10),
    ([4, 2, 4, 5, 1], 2, 10),
]
for nums, k, expected in cases:
    print("nums", nums, "k:", k, "smallest largest sum:", expected)

The first row allows one part, so the whole total of 32 is the answer. More parts can only push the largest sum down, never up.

Intuition: try the cuts for two parts

The first idea for two parts tries every single cut. Each cut gives two part sums, and the larger one is that cut's score. The best cut has the lowest score.

nums = [7, 2, 5, 10, 8]
best = None
for cut in range(1, len(nums)):
    left = sum(nums[:cut])
    right = sum(nums[cut:])
    score = max(left, right)
    print("cut after index", cut - 1, "-> parts", nums[:cut], "and", nums[cut:], "largest:", score)
    if best is None or score < best:
        best = score
print("best largest sum for k = 2:", best)

Four cuts settle the two-part question. The trap is the growth. Three parts choose two cut positions, four parts choose three, and the combinations multiply fast.

Brute force: rate every split

The brute force tries every way to place the cuts. A recursive walk fixes one part at a time and rates each complete split by its largest part sum. A counter records the complete splits rated.

def brute_split(nums, k):
    tried = 0

    def best_from(start, parts_left):
        nonlocal tried
        if parts_left == 1:
            tried += 1
            return sum(nums[start:])
        best = None
        running = 0
        for end in range(start, len(nums) - parts_left + 1):
            running += nums[end]
            rest = best_from(end + 1, parts_left - 1)
            candidate = max(running, rest)
            if best is None or candidate < best:
                best = candidate
        return best

    answer = best_from(0, k)
    return answer, tried

for nums, k in [([7, 2, 5, 10, 8], 2), ([7, 2, 5, 10, 8], 3), ([1, 2, 3, 4, 5, 6], 3), ([1, 2, 3, 4, 5, 6, 7, 8, 9], 4)]:
    answer, tried = brute_split(nums, k)
    print("nums", nums, "k:", k, "answer:", answer, "splits rated:", tried)

Nine values with four parts already rate 56 complete splits. Each split also costs a scan of its parts. The count grows combinatorially, and long arrays make it hopeless.

The optimal solution: binary search over candidate limits

A feasibility check asks whether a candidate limit allows at most k parts, and binary searching the smallest limit the check accepts gives the answer. That one sentence is the whole method.

The check is greedy. It fills each part as far as the limit permits, then starts a new part. Filling greedily never uses more parts than any other split under the same limit.

Feasibility is monotone. A larger limit never needs more parts, so the yes answers form one unbroken run above the true answer. A monotone question can be binary searched.

def parts_needed(nums, limit):
    parts = 1
    running = 0
    for value in nums:
        if running + value > limit:
            parts += 1
            running = value
        else:
            running += value
    return parts


def split_array(nums, k):
    lo = max(nums)
    hi = sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(nums, mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

cases = [
    ([7, 2, 5, 10, 8], 1, 32),
    ([7, 2, 5, 10, 8], 2, 18),
    ([7, 2, 5, 10, 8], 3, 14),
    ([10, 2, 2, 4, 5, 2], 3, 10),
    ([4, 2, 4, 5, 1], 2, 10),
]
for nums, k, expected in cases:
    result = split_array(nums, k)
    print("nums", nums, "k:", k, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. The search range starts at the largest single value and ends at the total. No limit outside that range can be the answer.

Walkthrough: the search on [7, 2, 5, 10, 8] with k = 2

The range opens at the largest value, 10, and the total, 32. Each probe runs the greedy check once and prints the part count. The search keeps the feasible half and discards the other.

def parts_needed(nums, limit):
    parts = 1
    running = 0
    for value in nums:
        if running + value > limit:
            parts += 1
            running = value
        else:
            running += value
    return parts


def split_traced(nums, k):
    lo = max(nums)
    hi = sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        parts = parts_needed(nums, mid)
        if parts <= k:
            print("limit", mid, "needs", parts, "parts -> feasible, search lower")
            hi = mid
        else:
            print("limit", mid, "needs", parts, "parts -> too many, search higher")
            lo = mid + 1
    return lo

print("answer:", split_traced([7, 2, 5, 10, 8], 2))

The limit 21 fits two parts with room to spare, so the search looks lower. The limit 15 forces three parts, so the search looks higher. Four probes settle on 18, the split [7, 2, 5] and [10, 8].

Complexity

The brute force rates every combination of cut positions, and each rating scans the array, so its time grows combinatorially in n and k. The search runs one greedy pass per probe, and the probes halve a numeric range, so its time is O(n log S) for a total sum S.

Both methods store only counters and running sums besides the input, so their extra space is O(1) apart from the brute force's recursion depth. The counts below compare splits rated against greedy passes run.

from math import comb

def parts_needed(nums, limit):
    parts = 1
    running = 0
    for value in nums:
        if running + value > limit:
            parts += 1
            running = value
        else:
            running += value
    return parts


def search_passes(nums, k):
    lo = max(nums)
    hi = sum(nums)
    passes = 0
    while lo < hi:
        mid = (lo + hi) // 2
        passes += 1
        if parts_needed(nums, mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return passes

for n in [5, 10, 20]:
    nums = list(range(1, n + 1))
    k = n // 2
    passes = search_passes(nums, k)
    print("values:", n, "k:", k, "- splits the brute force rates:", comb(n - 1, k - 1), " greedy passes:", passes, " values visited:", passes * n)

At 20 values the brute force rates 92,378 splits. The search runs 7 passes and visits 140 values. The trade is a clever question for an enumeration.

Edge cases and pitfalls

One part forces the whole total. As many parts as values forces the largest single value. Both extremes fall out of the search range endpoints with no special code.

def parts_needed(nums, limit):
    parts = 1
    running = 0
    for value in nums:
        if running + value > limit:
            parts += 1
            running = value
        else:
            running += value
    return parts


def split_array(nums, k):
    lo = max(nums)
    hi = sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(nums, mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return lo


def greedy_parts(nums, limit):
    parts = []
    current = []
    running = 0
    for value in nums:
        if running + value > limit and current:
            parts.append(current)
            current = []
            running = 0
        current.append(value)
        running += value
    parts.append(current)
    return parts

nums = [7, 2, 5, 10, 8]
print("k = 1:", split_array(nums, 1))
print("k = n:", split_array(nums, 5))
print("single value:", split_array([6], 1))
print("all equal, k = 2:", split_array([4, 4, 4, 4], 2))
print("greedy parts at limit 9:", greedy_parts(nums, 9))

The last line shows the classic pitfall. A limit below the largest value lets the greedy walk place 10 alone in a part. That part sums to 10 and breaks the very limit being tested, yet the part count of four looks like an ordinary answer. Starting the search at the largest value rules the trap out.