Split Array Largest Sum in Python (Minimize Largest Subarray Sum)

Binary search + greedy check to split an array into k subarrays while minimizing the largest subarray sum.

Medium Python 3.6+ Aug 9, 2026 Algorithms & data structures 15 views 0 copies

binary-search greedy array optimization split

Python code

33 lines

Python 3.6+

def can_split(nums, k, max_sum):
    subarrays = 1
    current_sum = 0
    for num in nums:
        if current_sum + num <= max_sum:
            current_sum += num
        else:
            subarrays += 1
            current_sum = num
            if subarrays > k:
                return False
    return True

def split_array_largest_min_sum(nums, k):
    left = max(nums)
    right = sum(nums)
    
    while left < right:
        mid = (left + right) // 2
        if can_split(nums, k, mid):
            right = mid
        else:
            left = mid + 1
    
    return left

if __name__ == "__main__":
    arr = [7, 2, 5, 10, 8]
    k = 2
    result = split_array_largest_min_sum(arr, k)
    print(f"Array: {arr}")
    print(f"Split into {k} subarrays")
    print(f"Minimized largest sum: {result}")

Output

stdout

Array: [7, 2, 5, 10, 8]
Split into 2 subarrays
Minimized largest sum: 18

# Splitting as [7, 2, 5] and [10, 8] → sums 14 and 18 → largest is 18
# No split into 2 subarrays has largest sum < 18

How it works

The solution uses binary search over the possible range of the largest sum (from max(nums) to sum(nums)). For each candidate mid, the can_split function greedily packs numbers into subarrays without exceeding mid. If the count of subarrays stays within k, the candidate is feasible, and we try lower values; otherwise, we increase the bound. The helper is O(n) per check, and binary search adds O(log(sum)) iterations, giving O(n log S) overall. The key trick is converting an optimization problem ('minimize max subarray sum') into a decision problem ('can we split with max sum <= X').

Common mistakes

Starting the binary search from 0 instead of `max(nums)` — a subarray must contain at least the largest single element.
Using `current_sum > max_sum` to start a new subarray instead of checking before adding the next number.
Forgetting to reset `current_sum` to the current number (not 0) when starting a new subarray.
Off-by-one in the binary search bounds — ensuring `left = mid + 1` and `right = mid` correctly maintains the invariant.

Variations

Use `functools` and a segment tree for a more complex O(n log n) solution with divide-and-conquer.
Return the actual split subarrays (track indices) instead of just the minimized largest sum.

Real-world use cases

Distributing a workload across k worker processes to minimize the maximum processing time or memory per worker.
Splitting a long log file into k chunks for parallel parsing while bounding the largest chunk size.
Partitioning dataset batches for distributed training so the largest batch fits memory limits.

Split Array Largest Sum in Python (Minimize Largest Subarray Sum)

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes