← DSA Atlas
Dedicated problem page · #410

Split Array Largest Sum

HardBinary SearchBinary search on the answer with a greedy feasibility checkBinary search on answer plus greedy partitioning
Solve on LeetCode ↗
410
HardBinary SearchBinary search on answer plus greedy partitioningBinary search on the answer with a greedy feasibility check

Split Array Largest Sum

Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays so that the largest sum among those subarrays is as small as possible, and return that minimized largest sum.

Open official problem prompt ↗
In plain English

Choose split points so the heaviest resulting subarray is as light as possible, and report that weight.

Picture it like this

Loading trucks that drive a fixed route in order: you fix a weight limit, load boxes onto a truck until the next box would exceed it, then start a new truck. The tightest limit that still fits everything into k trucks is the answer.

Example
Input
nums = [7,2,5,10,8], k = 2
Output
18
Why
Splitting into [7,2,5] (sum 14) and [10,8] (sum 18) gives a maximum of 18, the smallest achievable.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= k <= min(50, nums.length)
Pattern lesson

See the pattern, then code

Binary search on the answer with a greedy feasibility check
Recognition clue

'Minimize the maximum' over contiguous splits, where checking a fixed cap is easy but constructing the split is hard, is the hallmark of binary-searching the answer.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. If a cap C is allowed as the largest subarray sum, greedily filling subarrays until they would exceed C tells you the minimum number of pieces needed. Fewer required pieces than allowed means C is feasible, and feasibility is monotonic in C, so binary-search the smallest feasible cap.

New words, made simpleKnow these before the algorithm
Feasibility check
A fast test of whether a candidate answer is achievable
Monotonicity
Larger caps are always at least as feasible as smaller ones
Greedy packing
Filling each subarray to the cap before opening the next
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
DP over splits

Correct and classic but noticeably slower for large n.

dp[i][j] = min largest sum splitting the first i elements into j parts.

Time O(n^2 * k)Space O(n*k)
Best choiceBinary search on the answer

Simplest and fastest; the feasibility test is a single linear pass.

Search the cap in [max(nums), sum(nums)] using a greedy count as the feasibility test.

Time O(n log(sum))Space O(1)
The rule we keep true

Invariant

The optimal answer always lies in [lo, hi]; every cap >= hi is known feasible and every cap < lo is known infeasible.

Why this is correct

Reasoning

The largest sum must be at least max(nums) (one element cannot be split) and at most sum(nums) (a single part). The greedy count returns the fewest subarrays achievable for a cap, and needing <= k parts is monotonic in the cap, so binary search converges on the smallest feasible cap, which is exactly the minimized largest sum.

The algorithm in three movesSay these aloud before coding
1Set lo = max(nums) and hi = sum(nums)

lo=10 hi=32 mid=21 -> needs 2 pieces <= 2, hi=21

2For a candidate cap, greedily count the subarrays needed

lo=10 hi=21 mid=15 -> needs 3 pieces > 2, lo=16

3If the count is <= k the cap works, so lower hi to mid

lo=16 hi=21 mid=18 -> needs 2 pieces <= 2, hi=18

4Otherwise raise lo to mid + 1

lo=16 hi=18 mid=17 -> needs 3 pieces > 2, lo=18; lo==hi=18

5Return lo, the smallest feasible largest sum

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
70
21
52
103
84
1 · Readlo=10, hi=32
2 · AskDoes cap 21 fit in 2 parts?
3 · Update statemid=21, greedy needs 2
4 · ResultFeasible, hi = 21
Key takeaway

The search narrows the cap until the array just fits into 2 subarrays, yielding 18.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-11Greedy feasibility test

    Count subarrays by starting a new one whenever adding x would exceed the cap; feasible if that count is at most k.

  2. 2
    Lines 12Bound the answer

    It can never be below the largest element nor above the total sum.

  3. 3
    Lines 13-18Search the cap

    Feasible caps pull hi down; infeasible caps push lo up.

  4. 4
    Lines 19Return the minimized maximum

    lo is the tightest cap that still allows a valid k-way split.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k = 1 (answer is sum of all elements)
  • k = len(nums) (answer is max element)
  • Array containing zeros
  • Single-element array
!

Common beginner mistakes

  • Starting lo at 0 or sum instead of max(nums), breaking the greedy invariant
  • Counting splits starting from 0 instead of 1
  • Using cur + x >= cap instead of > cap, wrongly rejecting a cap that exactly fits
Check your understanding

Why is the lower bound of the search max(nums) rather than 0?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search