Split Array Largest Sum

You are given an integer array nums and an integer k.

Split nums into k non-empty subarrays — contiguous blocks that together cover the whole array, in their original order. Every split is judged by a single number: the largest subarray sum it produces.

Return the smallest possible value of that largest sum — in other words, choose the split that minimizes the maximum subarray sum.

A subarray is a contiguous part of the array.

Hints

· Stuck? Reveal one nudge at a time.

The answer is a single number, not a split. What is the smallest value it could possibly be? What is the largest?

Fix a candidate cap and ask a yes/no question: can the array be split into at most k pieces where no piece's sum exceeds the cap? One greedy left-to-right pass answers it.

That yes/no answer flips from no to yes exactly once as the cap grows — feasibility is monotone. Binary search the cap between max(nums) and sum(nums).

Common doubts

Every element must live inside some subarray, so whichever piece contains the largest element already has a sum of at least max(nums). No split can score below that.

With non-negative values, packing each piece as full as the cap allows never hurts — closing a piece early only forces elements into later pieces sooner. So the greedy count is a true minimum, and comparing it against k decides feasibility.

If the greedy pass fits everything in fewer than k pieces, you can always cut some piece into smaller ones — sums only shrink when values are non-negative. So any cap feasible with fewer pieces is also feasible with exactly k.

No. Feasibility is monotone: infeasible caps form a prefix of the range and feasible caps a suffix. The lower-bound loop converges exactly on the first feasible cap, which observation-by-observation is the minimized largest sum.

Interview follow-ups

· What an interviewer asks next.

Both pillars collapse: growing a piece can shrink its sum, so the greedy pass no longer computes the fewest pieces, and feasibility stops being monotone in the cap. Fall back to the partition DP, which never relies on either property.

It becomes multiway partitioning — scheduling jobs on k machines to minimize the busiest machine (makespan). That version is NP-hard; you would discuss greedy heuristics like sorting descending plus best-fit, or exhaustive search with pruning for small n.

Yes — after the binary search settles on the final cap, run the greedy pass once more with that cap and record the index where each piece closes. Those boundaries reconstruct an optimal split.

Fun facts

This problem is a disguise of the classic painter's partition problem: painters must paint a row of fence boards in order, and you minimize the time the busiest painter works.
The binary-search-on-the-answer skeleton here is reusable almost verbatim: Koko Eating Bananas, Capacity to Ship Packages Within D Days, and Minimum Number of Days to Make m Bouquets all swap in a different one-pass checker under the same loop.

Asked at

GoogleAmazonMetaMicrosoftApple

Frequently Sometimes Occasionally

Example 1

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Splitting into [7,2,5] and [10,8] gives sums 14 and 18, so the largest sum is 18. No other split into two subarrays does better.

Example 2

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Splitting into [1,2,3] and [4,5] gives sums 6 and 9. Every other split forces a larger maximum.

Constraints

- 1 <= nums.length <= 1000 - 0 <= nums[i] <= 10^6 - 1 <= k <= min(50, nums.length)

Split Array Largest Sum is the capstone of a beautiful idea: when you cannot afford to search the input, search the answer. We will walk from a cap-raising brute force, through a classic partition DP, to a binary search over the answer space that finishes in O(n log S).

Prerequisites

Before you start

· Concepts used directly in the solution.

Prefix sums. Precomputing running totals so any contiguous block's sum is one subtraction — the DP leans on this.

Greedy feasibility check. A single left-to-right pass that answers a yes/no question: can the array be split under a given cap using at most k parts?

Binary search on a monotone predicate. The lower-bound pattern — finding the first value where a yes/no answer flips from no to yes.

Understand the problem

In plain English: place k - 1 cuts in the array. Each way of cutting produces k contiguous chunks; its score is the largest chunk sum. Return the minimum score over all possible cuts.

Worked example — nums = [7,2,5,10,8], k = 2

cap 18:   [7  2  5] | [10  8]
           sum 14     sum 18     largest = 18  ✓ best possible
cap 17:   [7 2 5] [10] [8]   → needs 3 parts, but k = 2  ✗
answer: 18

Clarifying questions

A senior candidate pins down the input guarantees before writing a line — it changes which technique is even legal here.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are all the values non-negative?”

Critical. The greedy feasibility check and the monotonicity argument both rely on sums never shrinking as a block grows. Negative numbers would push you to the DP instead.

“Is k guaranteed to be at most the length of the array?”

Yes — otherwise k non-empty subarrays are impossible and the problem has no answer.

Edge cases

“What if k equals 1?”

The only split is the whole array — the answer is the total sum. A free sanity check for your code.

“What if k equals the array length?”

Every element sits alone — the answer is the maximum element. The other end of the same sanity check.

Constraints and scale

“How large can the total sum get?”

Up to 1000 elements of 10^6 — about 10^9. That rules out scanning every candidate answer and warns you to accumulate in 64-bit integers.

The ideal opening — say it like this

Before I start, I have a few clarifying questions.

Are all values non-negative, and is k guaranteed to be at most the array length?

If k is 1 or equal to the length, the answer is just the total sum or the maximum element — I will treat those as sanity checks on whatever I build.

Key observations

1Aha

The answer is a single number in a known range

Stop thinking about splits and think about the value of the answer. It can never be below max(nums) — the largest element must live inside some piece. It can never be above sum(nums) — that is what k = 1 scores. So the answer sits on a number line between max(nums) and sum(nums). We can search that line instead of enumerating splits.

2Aha

Feasibility is monotone in the cap

Ask a yes/no question about any cap C: can the array be split into at most k pieces, each with sum at most C? If the answer is yes for C, it is yes for every larger cap — extra headroom never hurts. So the number line looks like a wall of no answers followed by a wall of yes answers, and the answer to the whole problem is the first yes.

cap:       10  …  16   17   18   19  …  32
fits k=2?  no  …  no   no   YES  YES …  YES
                             ^ first yes = answer

3Aha

One greedy pass computes the fewest pieces for any cap

To answer the yes/no question for a cap, walk left to right and pack each piece as full as it can get: when adding the next element would push the running sum past the cap, close the piece and start a new one. Because values are non-negative, closing a piece early can never help — so this pass yields the fewest pieces possible. The cap is feasible exactly when that count is at most k (if it is below k, cut any piece further; sums only shrink).

Brute force vs optimal

	Brute force	DP	Binary search
Time	O(n · S)	O(k · n²)	O(n log S)
Space	O(1)	O(n)	O(1)

Here S is sum(nums) — up to about 10^9. The full code for all three approaches lives in the Approaches selector below.

Summary

Key takeaway

When a problem asks you to minimize a maximum (or maximize a minimum), the answer is a single number on a bounded range, and feasibility of a guess is monotone with a cheap checker — binary search the answer, not the input. The greedy pass is the checker; the binary search does the optimizing.

lo = max(nums), hi = sum(nums)
while lo < hi:
    mid = (lo + hi) / 2
    if partsNeeded(mid) <= k:  hi = mid     # feasible — try smaller
    else:                      lo = mid + 1 # infeasible — must raise
return lo