Generated by Codex with GPT-5

Quick facts

  • Difficulty: HARD
  • Problem: Split Array Largest Sum
  • Main tags: Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum

What the problem is really asking

The input array must be cut into exactly k non-empty, contiguous pieces. Each cut creates one subarray, and the score of a split is the largest subarray sum that appears anywhere in that split.

The goal is to make that worst subarray sum as small as possible.

That wording matters because the problem is not asking for the total sum, the average sum, or the most balanced-looking split. It is a classic minimax problem: choose the partitioning whose biggest piece is as small as possible.

For the standard example nums = [7, 2, 5, 10, 8] and k = 2:

  • splitting as [7, 2, 5] | [10, 8] gives largest sum 18
  • splitting as [7, 2] | [5, 10, 8] gives largest sum 23

So the correct answer is 18, because that is the smallest possible value of the largest part.

Two useful ways to think about it

The first natural solution is dynamic programming.

If prefix[i] is the sum of the first i elements, then a DP state can be:

dp[i][parts] = minimum possible largest subarray sum when splitting nums[:i] into exactly parts pieces

To fill that state, the last piece can start at any earlier index cut, so:

dp[i][parts] = min(max(dp[cut][parts - 1], prefix[i] - prefix[cut]))

That is a valid and important way to derive the problem, because it makes the minimax structure obvious. But it is usually O(k * n^2), which is slower than needed for this problem.

The better interview insight is to stop asking, “Where should the cuts go?” and instead ask, “If I guess the answer value, can I check whether that guess is feasible?”

Suppose the guessed answer is limit. Then the question becomes:

“Can the array be split into at most k contiguous subarrays so that every subarray sum is at most limit?”

That reframing is powerful because it turns the problem into a yes-or-no feasibility test.

Why binary search plus greedy is the optimal approach

The answer must live in a fixed numeric range:

  • it can never be smaller than max(nums), because some subarray must contain the largest single element
  • it can never be larger than sum(nums), because taking the whole array as one part gives that value

Now focus on one guessed limit.

Because all numbers are non-negative in this problem, the best way to check feasibility is greedy:

  1. Scan from left to right.
  2. Keep adding numbers to the current subarray while the sum stays at most limit.
  3. The moment the next number would exceed limit, start a new subarray.

This greedy rule is correct because delaying a cut never hurts when numbers are non-negative. Packing each subarray as full as possible gives the fewest subarrays needed for that limit.

That is exactly what the feasibility check needs:

  • if greedy needs more than k subarrays, the limit is too small
  • if greedy needs k or fewer, the limit is feasible

And that predicate is monotonic:

  • if a limit works, every larger limit also works
  • if a limit fails, every smaller limit also fails

Once the problem has that monotonic shape, binary search on the answer is the right tool.

A concrete example

Take nums = [7, 2, 5, 10, 8] and k = 2.

Try limit = 17:

  • pack greedily: [7, 2, 5] has sum 14
  • adding 10 would exceed 17, so cut there
  • next part is [10]
  • adding 8 would exceed 17, so cut again
  • final part is [8]

That uses 3 subarrays, so 17 is too small.

Try limit = 18:

  • [7, 2, 5] has sum 14
  • adding 10 would exceed 18, so cut
  • next part [10, 8] has sum 18

That uses exactly 2 subarrays, so 18 works.

Since 17 fails and 18 works, the minimum feasible answer is 18.

How to derive this in an interview

A clean derivation sounds like this:

  1. Start with the minimax interpretation: minimize the largest subarray sum.
  2. Notice that directly choosing cut positions leads naturally to DP.
  3. Ask whether a guessed answer can be verified efficiently.
  4. Realize that for a fixed limit, the fewest required subarrays can be found greedily because all values are non-negative.
  5. Use binary search over the answer range because feasibility changes from false to true only once.

That explanation shows understanding, not just memorization.

Python solution

from typing import List


class SplitArrayLargestSumSolver:
    """Compute the minimum possible largest subarray sum."""

    def minimum_largest_sum(self, numbers: List[int], partition_count: int) -> int:
        """
        Binary search the answer space from max(numbers) to sum(numbers).

        For each candidate limit, greedily count how many partitions are needed
        if no partition is allowed to exceed that limit.
        """
        if not numbers:
            return 0

        lower_bound = max(numbers)
        upper_bound = sum(numbers)

        while lower_bound < upper_bound:
            candidate_limit = lower_bound + (upper_bound - lower_bound) // 2
            partitions_needed = self._minimum_partitions_needed(
                numbers=numbers,
                allowed_max_sum=candidate_limit,
            )

            if partitions_needed <= partition_count:
                upper_bound = candidate_limit
            else:
                lower_bound = candidate_limit + 1

        return lower_bound

    def _minimum_partitions_needed(
        self,
        numbers: List[int],
        allowed_max_sum: int,
    ) -> int:
        """
        Return the fewest contiguous partitions needed when each partition sum
        must stay at or below allowed_max_sum.

        Because the input values are non-negative, greedily filling the current
        partition as much as possible minimizes the number of partitions used.
        """
        partitions_used = 1
        current_partition_sum = 0

        for number in numbers:
            if current_partition_sum + number <= allowed_max_sum:
                current_partition_sum += number
                continue

            # Starting a new partition is forced here; keeping `number` in the
            # current partition would violate the candidate limit.
            partitions_used += 1
            current_partition_sum = number

        return partitions_used


class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        solver = SplitArrayLargestSumSolver()
        return solver.minimum_largest_sum(numbers=nums, partition_count=k)

Why this works

The lower bound max(nums) is necessary because no partition can avoid containing the largest element. The upper bound sum(nums) is always possible by placing the entire array into one partition.

For any candidate limit, the greedy scan computes the minimum number of partitions required to keep every partition sum at or below that limit. The key fact is non-negativity: once adding the next number would exceed the limit, there is no benefit to waiting longer before cutting, because future additions only make the sum larger. So the greedy strategy is forced and optimal for the feasibility check.

That means the algorithm can correctly answer whether a limit is feasible. Since feasibility is monotonic, binary search finds the smallest feasible limit, which is exactly the minimum possible largest subarray sum.

The runtime is O(n log S), where n is the array length and S = sum(nums) - max(nums) + 1 is the size of the search range. The extra space is O(1) aside from the input.

Interview follow-ups

Why is checking for at most k partitions enough when the problem asks for exactly k?

If a limit allows the array to be split into fewer than k partitions, that still means the limit is feasible for the original problem. The reason is that every partition is contiguous and non-empty, and the array length is at least k, so any partition containing more than one element can be split again into smaller contiguous pieces. Because all numbers are non-negative, splitting a partition cannot increase the maximum partition sum beyond the original partition’s sum. So <= k is enough for the check, even though the final problem statement says exactly k.

What if the interviewer wants the actual partition boundaries, not just the minimum largest sum?

The binary search still finds the optimal limit first. After that, a second pass can reconstruct one valid partitioning. A common way is to walk from right to left, keeping a running sum and forcing a cut whenever adding the next value would exceed the optimal limit or whenever the number of remaining elements must match the number of remaining partitions. That reconstruction step is linear, so the asymptotic complexity stays the same up to constant factors. The important tradeoff is code complexity: computing only the minimum value is simpler, while reconstructing boundaries requires extra bookkeeping.

What changes if negative numbers are allowed in the array?

That is where the greedy feasibility check stops being reliable. With negative values, a partition that looks too large right now might later be reduced by a negative number, so the “cut as soon as the limit would be exceeded” rule is no longer obviously optimal. The monotonic answer-space idea can also become trickier to justify. In that variant, dynamic programming is the safer framework because it reasons directly about cut positions instead of relying on the special structure created by non-negative numbers.

When is the dynamic programming solution worth discussing?

It is worth discussing when the interviewer cares about derivation, variants, or proof technique. The DP recurrence makes the problem structure very explicit: every final answer comes from choosing the last cut and taking the worse of the previous optimum and the last segment sum. That framing generalizes better to variants where the greedy feasibility check breaks. The tradeoff is runtime: the standard DP is much slower than binary search plus greedy on the original LeetCode constraints, so it is usually the right explanation to mention but not the final implementation to code unless the interviewer pushes in that direction.

Practical takeaway

The decisive move is to treat the answer itself as the search space.

Once the problem is reframed as “find the smallest maximum subarray sum that is still feasible,” the rest becomes clean: greedy tells how many partitions a candidate limit requires, and binary search finds the first limit that works.