← Back to DSA Animator
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.