Split Array Largest Sum Solution

Problem

Given an array of non-negative integers and an integer k, partition the array into exactly k contiguous, non-empty subarrays so that the largest subarray sum is as small as possible. Return that minimum possible largest sum.

Input: nums = [7, 2, 5, 10, 8], k = 2
Output: 18
Explanation: Splitting as [7, 2, 5] and [10, 8] gives a maximum subarray sum of 18, which is better than any other 2-way split.

Intuition

The answer must be at least max(nums) — one subarray always contains the largest element — and at most sum(nums) — the case where k = 1. This bounded range makes the problem amenable to binary search on the answer itself: for any candidate limit, a single greedy pass determines whether the array can be partitioned into k subarrays that each stay within that limit.

Approach 1 — Dynamic Programming

Build a table where dp[i][j] is the minimum possible largest sum when splitting the first i elements into j groups. For each state, try every position m as the start of the last group and take the minimum.

Precompute prefix sums to evaluate any subarray sum in O(1).
Initialize dp[0][0] = 0; all other entries start at infinity.
For each prefix length i and group count j, iterate over all split points m (last group is nums[m..i-1]).
Update dp[i][j] = min(dp[i][j], max(dp[m][j-1], prefix_sum[i] - prefix_sum[m])).
Return dp[n][k].

1def splitArray(nums: list[int], k: int) -> int:
2    n = len(nums)
3    prefix_sum = [0] * (n + 1)
4    for i in range(n):
5        prefix_sum[i + 1] = prefix_sum[i] + nums[i]
6
7    INF = float('inf')
8    dp = [[INF] * (k + 1) for _ in range(n + 1)]
9    dp[0][0] = 0
10
11    for i in range(1, n + 1):
12        for j in range(1, min(i, k) + 1):
13            for m in range(j - 1, i):  # last group spans nums[m..i-1]
14                last_group_sum = prefix_sum[i] - prefix_sum[m]
15                candidate = max(dp[m][j - 1], last_group_sum)
16                if candidate < dp[i][j]:
17                    dp[i][j] = candidate
18
19    return dp[n][k]

Time: O(n² × k) — three nested loops over prefix length, group count, and split point.

Space: O(n × k) for the dp table; O(n) additional for prefix sums.

Approach 2 — Binary Search on Answer

Binary search between max(nums) (the minimum possible answer) and sum(nums) (the maximum). For each candidate limit, greedily assign elements to the current subarray; whenever adding the next element would exceed the limit, open a new subarray. If the total subarray count stays within k, the limit is achievable.

Set lo = max(nums), hi = sum(nums).
While lo < hi, compute mid = (lo + hi) // 2.
Run a greedy pass: accumulate elements into a group; when adding num would exceed mid, increment group count and start fresh with num.
If group count ≤ k, the limit mid works — shrink the window by setting hi = mid.
Otherwise, the limit is too tight — raise the floor with lo = mid + 1.
Return lo.

1def splitArray(nums: list[int], k: int) -> int:
2    def can_fit(limit: int) -> bool:
3        group_count = 1
4        current_sum = 0
5        for num in nums:
6            if current_sum + num > limit:
7                group_count += 1       # start a new subarray
8                current_sum = num
9                if group_count > k:
10                    return False
11            else:
12                current_sum += num
13        return True
14
15    lo, hi = max(nums), sum(nums)
16    while lo < hi:
17        mid = (lo + hi) // 2
18        if can_fit(mid):
19            hi = mid        # valid limit; try to tighten it
20        else:
21            lo = mid + 1    # limit too small; raise the floor
22    return lo

Time: O(n × log(sum(nums))) — log iterations of binary search, each requiring an O(n) greedy pass.

Space: O(1) — only a handful of counters and accumulators beyond the input.

Complexity Summary

Approach	Time	Space	When to use
Dynamic Programming	O(n² × k)	O(n × k)	When n and k are both small and you need a table-based recurrence for debugging or extension
Binary Search on Answer	O(n log(sum))	O(1)	Almost always preferred — dramatically faster and uses constant extra memory

Common Mistakes

Setting lo = 0 instead of lo = max(nums) — if the limit is less than the largest element, the greedy check will immediately try to open a second group for that element alone, inflating the count; the bound max(nums) makes every individual element valid.
Using hi = mid - 1 in the binary search update — this skips the case where mid is exactly the answer; always use hi = mid when searching for the minimum valid value and lo < hi as the loop condition.
Starting group_count at 0 — the array is never empty; there is always at least one group in progress, so initialize to 1.
Initializing lo and hi with regular int in Java/C++ — sum(nums) can exceed Integer.MAX_VALUE for large inputs; use long throughout or you risk silent overflow in the midpoint calculation.
Forgetting that the greedy pass assigns each element to exactly one group — a common variant bug is skipping the current element when starting a new group, which would leave it unassigned; the new group starts with current_sum = num, not current_sum = 0.

Split Array Largest Sum — Solution