DSA AnimatorDSA animations
Split Array Largest Sum LC #410 Hard Binary Search on Answer
Problem

Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.

Example 1
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: Best split [7,2,5] | [10,8] → max(14, 18) = 18.
Example 2
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: Best split [1,2,3] | [4,5] → max(6, 9) = 9.
Example 3
Input: nums = [1,4,4], k = 3
Output: 4
Explanation: Split each into its own subarray: max(1,4,4) = 4.
Constraints: 1 ≤ nums.length ≤ 1000  |  0 ≤ nums[i] ≤ 10⁶  |  1 ≤ k ≤ min(50, nums.length)
Try Examples
Custom:
Max Subarray Sum — Binary Search Range
lo = — hi = —
Searching for minimum feasible maximum sum
Greedy Split Simulation (mid = —)
— splits
vs k = —
Min answer: —
State Variables
lo
—
hi
—
mid
—
splits
—
feasible?
—
Step Logic
Press Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
lo = max(nums), hi = sum(nums) — search space boundaries
2
mid = (lo+hi)/2 — candidate max subarray sum to test
3
Greedy feasibility: count splits with max sum ≤ mid
4
If splits ≤ k → feasible: hi = mid (try smaller sum)
5
If splits > k → infeasible: lo = mid+1 (need bigger sum)
6
Return lo = minimum feasible largest subarray sum
Time
O(n log S)
Space
O(1)
Why Binary Search Works

The feasibility function is monotone: if we can split nums into ≤ k subarrays with max sum ≤ M, then we can certainly do the same with max sum ≤ M+1. This monotone property lets us binary search for the minimum M that is still feasible. S = sum(nums) is the size of the search space.

Greedy check: Scan left→right, accumulate current sum. When the next element would push us over mid, start a new partition. Count partitions needed.

How to solve Split Array Largest Sum

LeetCode 410 · Hard · Binary Search · Pattern: Binary Search on Answer

Why the obvious approach is slow

Trying every way to place the cuts grows very fast. Dynamic programming works, but binary search is simpler and faster.

The key idea

Guess a limit for the largest sum. Fill parts greedily, and count how many parts that limit needs. If it needs at most k parts, the limit works, so try smaller.

Remember

Minimize the largest part sum by binary searching that sum. This same template solves shipping, books and painters.

Run the animation above on your own input, or watch the 1:09 video explanation of Split Array Largest Sum with a dry run and Java code.

More Binary Search problems