We have an array and we need to split it into exactly k contiguous groups. Each group has a sum, and we want to minimize the maximum of those sums. Think of it like distributing work across k workers who must each handle a contiguous chunk, and we want to make the heaviest workload as light as possible.

The constraint that matters is that the subarrays must be contiguous. We cannot pick arbitrary elements for a group. We only choose where to place k - 1 dividers in the array. With n - 1 possible divider positions and k - 1 dividers to place, the number of ways to split grows combinatorially.

The goal is not to make all subarrays equal. It is to minimize the worst case, the single largest subarray sum. This minimax structure is what allows both a dynamic programming and a binary search solution.

Key Constraints:

Intuition

Try every possible way of splitting the array. We place k - 1 dividers among the n - 1 gaps between elements, and for each configuration we compute the sum of each subarray, take the maximum, and track the overall minimum.

Recursion expresses this directly. At each step we decide where the current subarray ends, compute its sum, and recurse on the remaining array with one fewer split to make. The base case is when one split remains, where the entire remaining array forms the last subarray.

A prefix sum array lets us compute any subarray sum in O(1), which avoids re-adding elements on every recursive call.

Algorithm

Visualization and Code

The recursion recomputes the same subproblems repeatedly. The state solve(index, splitsLeft) depends only on those two values, yet it can be reached from many different earlier split choices. Caching each (index, splitsLeft) pair collapses the work to one computation per state, which is the basis for the dynamic programming approach.

Intuition

There are only n * k distinct states, one for each pair of array position and remaining split count, so caching turns the exponential recursion into a polynomial table fill.

Building the table bottom-up, let dp[j][i] represent the minimum possible largest sum when splitting the first i elements into j subarrays. To fill in dp[j][i], we try every possible position p for the start of the last subarray. The last subarray covers nums[p..i-1], and the first j-1 subarrays cover nums[0..p-1]. So dp[j][i] = min over all valid p of max(dp[j-1][p], sum(p..i-1)).

The base case is dp[1][i] = sum of the first i elements, because with one subarray, we must take everything.

Algorithm

Visualization and Code

The DP enumerates every split position. The answer itself is a single number within a bounded range, and the next approach searches that range directly, checking feasibility instead of constructing the split.

Intuition

Instead of asking "what is the best way to split?", flip the question to "given a maximum allowed subarray sum of X, can we split the array into k or fewer subarrays?"

That feasibility question has a greedy answer. Scan left to right, extending the current subarray as far as possible. When adding the next element would push the running sum past X, start a new subarray. Count the subarrays needed. If the count is at most k, then X is achievable.

The feasibility function is monotonic. If a max sum of X permits a valid split, then X + 1 permits the same split, so it is also feasible. If X does not permit a valid split, neither does X - 1. Feasibility flips from false to true at a single threshold, and that threshold is the answer, so binary search on X finds it.

The search range is [max(nums), sum(nums)]. The lower bound is max(nums), because the largest single element must fit inside some subarray no matter how the array is split. The upper bound is sum(nums), the value when k = 1 and one subarray holds everything.

Algorithm

Visualization and Code