Split Array Largest Sum
Description
Given an integer array nums and an integer k, split nums into exactly k non-empty contiguous subarrays such that the largest sum among all the subarrays is minimized.
A subarray is a contiguous portion of the original array — the elements must stay in their original order and cannot be rearranged. You must use every element exactly once across the k subarrays.
Among all possible ways to split the array into k parts, find the one where the maximum subarray sum is as small as possible, and return that minimized largest sum.
For example, if you have nums = [7, 2, 5, 10, 8] and k = 2, one way to split is [7, 2, 5] and [10, 8] with sums 14 and 18. The largest sum here is 18. Another split is [7, 2] and [5, 10, 8] with sums 9 and 23, giving a largest sum of 23. The first split is better because 18 < 23. The answer is 18 — the smallest possible largest sum across all valid splits.
Examples
Example 1
Input: nums = [7, 2, 5, 10, 8], k = 2
Output: 18
Explanation: There are four ways to split into two subarrays:
- [7] and [2, 5, 10, 8] → sums are 7 and 25 → largest = 25
- [7, 2] and [5, 10, 8] → sums are 9 and 23 → largest = 23
- [7, 2, 5] and [10, 8] → sums are 14 and 18 → largest = 18
- [7, 2, 5, 10] and [8] → sums are 24 and 8 → largest = 24
The minimum among {25, 23, 18, 24} is 18, achieved by splitting into [7, 2, 5] and [10, 8].
Example 2
Input: nums = [1, 2, 3, 4, 5], k = 2
Output: 9
Explanation: The best split is [1, 2, 3] and [4, 5] with sums 6 and 9. The largest sum is 9. Other splits like [1, 2, 3, 4] and [5] give sums 10 and 5 (largest = 10), which is worse.
Example 3
Input: nums = [1, 4, 4], k = 3
Output: 4
Explanation: When k equals the array length, each element becomes its own subarray: [1], [4], [4]. The sums are 1, 4, and 4. The largest is 4. There is no way to get a largest sum smaller than 4 since the element 4 must appear in some subarray.
Constraints
- 1 ≤ nums.length ≤ 1000
- 0 ≤ nums[i] ≤ 10^6
- 1 ≤ k ≤ min(50, nums.length)
Editorial
Brute Force
Intuition
The most direct way to solve this problem is to try every possible way to place the k - 1 partition points that divide the array into k subarrays, compute the maximum subarray sum for each configuration, and take the minimum across all configurations.
Think of it like cutting a loaf of bread. You have a bread of n slices, and you need to make k - 1 cuts to get k pieces. For each possible arrangement of cuts, you weigh each piece and note the heaviest one. After trying all arrangements, you pick the one where the heaviest piece weighed the least.
We can implement this with recursion. At each step, we decide where to end the first subarray. For each choice, the remaining elements are recursively split into k - 1 subarrays. The answer is the minimum, over all choices, of the maximum between the current subarray's sum and the result of the recursive call.
Step-by-Step Explanation
Let's trace through with nums = [7, 2, 5, 10, 8], k = 2.
We need to split the array into 2 subarrays. That means choosing where the first subarray ends.
Step 1: Try first subarray = [7], remaining = [2, 5, 10, 8] with k=1.
- First subarray sum = 7
- Remaining must form 1 subarray → sum = 2 + 5 + 10 + 8 = 25
- Max of {7, 25} = 25
Step 2: Try first subarray = [7, 2], remaining = [5, 10, 8] with k=1.
- First subarray sum = 9
- Remaining sum = 23
- Max of {9, 23} = 23
Step 3: Try first subarray = [7, 2, 5], remaining = [10, 8] with k=1.
- First subarray sum = 14
- Remaining sum = 18
- Max of {14, 18} = 18
Step 4: Try first subarray = [7, 2, 5, 10], remaining = [8] with k=1.
- First subarray sum = 24
- Remaining sum = 8
- Max of {24, 8} = 24
Step 5: Take the minimum across all choices: min(25, 23, 18, 24) = 18.
Result: The minimum possible largest sum is 18.
Brute Force — Trying All Split Points for k=2 — Watch how we try each possible split point, compute the maximum subarray sum for each split, and track the overall minimum.
Algorithm
- Define a recursive function
solve(start, k)that returns the minimized largest sum when splittingnums[start..n-1]intoksubarrays. - Base case: If
k == 1, the only option is to take all remaining elements as one subarray. Return their sum. - Recursive case: Try every possible end position for the first subarray:
- For each split point
ifromstartton - k(leaving at least one element for each remaining subarray):- Compute the sum of the first subarray
nums[start..i]. - Recursively solve
solve(i + 1, k - 1)for the rest. - Track the maximum of these two values.
- Compute the sum of the first subarray
- Return the minimum across all split choices.
- For each split point
- The answer is
solve(0, k).
Code
#include <vector>
#include <climits>
#include <numeric>
using namespace std;
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
return solve(nums, 0, k);
}
private:
int solve(vector<int>& nums, int start, int k) {
int n = nums.size();
if (k == 1) {
int total = 0;
for (int i = start; i < n; i++) total += nums[i];
return total;
}
int best = INT_MAX;
int currentSum = 0;
for (int i = start; i <= n - k; i++) {
currentSum += nums[i];
int worst = max(currentSum, solve(nums, i + 1, k - 1));
best = min(best, worst);
}
return best;
}
};class Solution:
def splitArray(self, nums: list[int], k: int) -> int:
def solve(start: int, k: int) -> int:
if k == 1:
return sum(nums[start:])
best = float('inf')
current_sum = 0
for i in range(start, len(nums) - k + 1):
current_sum += nums[i]
worst = max(current_sum, solve(i + 1, k - 1))
best = min(best, worst)
return best
return solve(0, k)class Solution {
public int splitArray(int[] nums, int k) {
return solve(nums, 0, k);
}
private int solve(int[] nums, int start, int k) {
if (k == 1) {
int total = 0;
for (int i = start; i < nums.length; i++) total += nums[i];
return total;
}
int best = Integer.MAX_VALUE;
int currentSum = 0;
for (int i = start; i <= nums.length - k; i++) {
currentSum += nums[i];
int worst = Math.max(currentSum, solve(nums, i + 1, k - 1));
best = Math.min(best, worst);
}
return best;
}
}Complexity Analysis
Time Complexity: O(n^k) in the worst case.
At each level of recursion, we try up to O(n) split positions, and we have k levels of recursion. This creates a recursion tree with up to n^k leaves. For n = 1000 and k = 50, this is astronomically large and completely infeasible.
Space Complexity: O(k) for the recursion stack depth. Each recursive call reduces k by 1, so the maximum recursion depth is k.
Why This Approach Is Not Efficient
The brute force recursion has exponential time complexity O(n^k). With n up to 1000 and k up to 50, the number of possible split configurations is impossibly large.
The core problem is redundant computation. The recursive function solve(start, k) is called with the same (start, k) pair many times from different paths in the recursion tree. For example, when splitting with k=3, multiple different first-split choices can lead to solving the same solve(5, 2) subproblem.
This overlapping subproblems pattern is a classic signal for dynamic programming. By storing the result of each (start, k) pair the first time we compute it, we avoid recomputing it exponentially many times.
Better Approach - Dynamic Programming
Intuition
The brute force recursion recomputes the same subproblems many times. We can fix this by using memoization or bottom-up dynamic programming.
Define dp[i][j] as the minimized largest sum when splitting the first i elements of the array into j subarrays. We want dp[n][k].
The key recurrence is:
dp[i][j] = min over all valid split points p of: max(dp[p][j-1], sum(nums[p..i-1]))
This says: to split the first i elements into j subarrays, try every position p where we could end the first j-1 subarrays. The last subarray would be nums[p..i-1]. The cost is the maximum of the best solution for the first p elements split into j-1 subarrays, and the sum of the last subarray.
We precompute a prefix sum array so that the sum of any subarray can be computed in O(1) time.
Step-by-Step Explanation
Let's trace with nums = [7, 2, 5, 10, 8], k = 2.
Prefix sums: [0, 7, 9, 14, 24, 32]
Step 1: Base case — dp[i][1] = sum of first i elements.
- dp[1][1] = 7, dp[2][1] = 9, dp[3][1] = 14, dp[4][1] = 24, dp[5][1] = 32
Step 2: Fill dp[i][2] for i from 2 to 5. For each i, try all split points p.
Step 3: dp[2][2]: Split first 2 elements into 2 subarrays.
- p=1: max(dp[1][1], sum(nums[1..1])) = max(7, 2) = 7
- dp[2][2] = 7
Step 4: dp[3][2]: Split first 3 elements into 2 subarrays.
- p=1: max(dp[1][1], sum(nums[1..2])) = max(7, 7) = 7
- p=2: max(dp[2][1], sum(nums[2..2])) = max(9, 5) = 9
- dp[3][2] = min(7, 9) = 7
Step 5: dp[4][2]: Split first 4 elements into 2 subarrays.
- p=1: max(7, 2+5+10) = max(7, 17) = 17
- p=2: max(9, 5+10) = max(9, 15) = 15
- p=3: max(14, 10) = 14
- dp[4][2] = min(17, 15, 14) = 14
Step 6: dp[5][2]: Split all 5 elements into 2 subarrays.
- p=1: max(7, 2+5+10+8) = max(7, 25) = 25
- p=2: max(9, 5+10+8) = max(9, 23) = 23
- p=3: max(14, 10+8) = max(14, 18) = 18
- p=4: max(24, 8) = 24
- dp[5][2] = min(25, 23, 18, 24) = 18
Result: dp[5][2] = 18.
DP Table — Building dp[i][j] for Split Array — Watch how we fill the DP table row by row. Each cell dp[i][j] represents the minimized largest sum when splitting the first i elements into j subarrays.
Algorithm
- Compute prefix sums so that the sum of any subarray
nums[l..r]can be found in O(1) asprefix[r+1] - prefix[l]. - Create a 2D DP table
dp[i][j]whereiranges from 1 to n andjfrom 1 to k. - Base case:
dp[i][1] = prefix[i](all first i elements in one subarray). - Transition: For
jfrom 2 to k, andifromjto n:- For each split point
pfromj-1toi-1:- Compute
candidate = max(dp[p][j-1], prefix[i] - prefix[p]) dp[i][j] = min(dp[i][j], candidate)
- Compute
- For each split point
- Return
dp[n][k].
Code
#include <vector>
#include <climits>
using namespace std;
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
// dp[i][j] = min largest sum splitting first i elements into j subarrays
vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, LLONG_MAX));
// Base case: 1 subarray
for (int i = 1; i <= n; i++) dp[i][1] = prefix[i];
for (int j = 2; j <= k; j++) {
for (int i = j; i <= n; i++) {
for (int p = j - 1; p < i; p++) {
long long lastSum = prefix[i] - prefix[p];
long long candidate = max(dp[p][j - 1], lastSum);
dp[i][j] = min(dp[i][j], candidate);
}
}
}
return (int)dp[n][k];
}
};class Solution:
def splitArray(self, nums: list[int], k: int) -> int:
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
# dp[i][j] = min largest sum splitting first i elements into j subarrays
dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
# Base case: 1 subarray
for i in range(1, n + 1):
dp[i][1] = prefix[i]
for j in range(2, k + 1):
for i in range(j, n + 1):
for p in range(j - 1, i):
last_sum = prefix[i] - prefix[p]
candidate = max(dp[p][j - 1], last_sum)
dp[i][j] = min(dp[i][j], candidate)
return dp[n][k]class Solution {
public int splitArray(int[] nums, int k) {
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
long[][] dp = new long[n + 1][k + 1];
for (long[] row : dp) java.util.Arrays.fill(row, Long.MAX_VALUE);
for (int i = 1; i <= n; i++) dp[i][1] = prefix[i];
for (int j = 2; j <= k; j++) {
for (int i = j; i <= n; i++) {
for (int p = j - 1; p < i; p++) {
long lastSum = prefix[i] - prefix[p];
long candidate = Math.max(dp[p][j - 1], lastSum);
dp[i][j] = Math.min(dp[i][j], candidate);
}
}
}
return (int) dp[n][k];
}
}Complexity Analysis
Time Complexity: O(n² × k)
We have k layers (for j), each layer iterates over O(n) values of i, and for each (i, j) we try O(n) split points p. The total is O(n² × k). With n = 1000 and k = 50, this is about 5 × 10^7 — feasible but on the edge.
Space Complexity: O(n × k) for the DP table. We store one value for each (i, j) combination.
Why This Approach Is Not Efficient
While the DP approach is a massive improvement over brute force (polynomial vs exponential), it still has O(n² × k) time complexity. For n = 1000 and k = 50, that is 50 million operations with non-trivial constant factors.
More importantly, there is a fundamentally different way to think about this problem that leads to O(n × log(sum)) time — often much faster in practice.
The key insight is a change of perspective: instead of asking "what is the minimum possible largest sum?", we ask "given a candidate largest sum S, can we split the array into at most k subarrays such that no subarray exceeds S?" This turns the optimization problem into a decision problem, which we can solve greedily in O(n) time. And since the answer is monotonic (larger S → easier to satisfy), we can binary search over S.
Optimal Approach - Binary Search on Answer
Intuition
Instead of directly finding the optimal split, we flip the question around: "If I set a maximum allowed sum per subarray to be S, can I split the array into at most k subarrays where no subarray exceeds S?"
This question can be answered greedily in O(n) time: scan through the array, accumulating a running sum. Whenever adding the next element would exceed S, start a new subarray. Count how many subarrays you need. If the count is ≤ k, then S is feasible.
The crucial observation is that this feasibility is monotonic:
- If S is feasible (can split into ≤ k subarrays), then any S' > S is also feasible (giving each subarray more room only helps).
- If S is infeasible (need > k subarrays), then any S' < S is also infeasible.
This monotonicity means we can binary search on S to find the smallest feasible value.
The search range is:
- Lower bound:
max(nums)— no subarray sum can be smaller than the largest element (since that element must be in some subarray). - Upper bound:
sum(nums)— putting everything in one subarray (corresponds to k = 1).
Think of it like packing books into boxes with a weight limit. If the weight limit is too low, you need too many boxes. If high enough, you can fit them in k boxes. You want the lowest weight limit that still works with k boxes.
Step-by-Step Explanation
Let's trace with nums = [7, 2, 5, 10, 8], k = 2.
Step 1: Set binary search bounds.
- left = max(7, 2, 5, 10, 8) = 10
- right = sum = 32
- result = -1
Step 2: Iteration 1: mid = (10 + 32) / 2 = 21
- Check feasible(21): Scan array with max_sum = 21.
- current = 0, subarrays = 1
- Add 7: current = 7 ≤ 21 ✓
- Add 2: current = 9 ≤ 21 ✓
- Add 5: current = 14 ≤ 21 ✓
- Add 10: current = 24 > 21 ✗ → new subarray, current = 10, subarrays = 2
- Add 8: current = 18 ≤ 21 ✓
- Total subarrays = 2 ≤ k = 2 → FEASIBLE
- result = 21, right = 20
Step 3: Iteration 2: mid = (10 + 20) / 2 = 15
- Check feasible(15):
- Add 7: current = 7
- Add 2: current = 9
- Add 5: current = 14 ≤ 15 ✓
- Add 10: current = 24 > 15 → new subarray, current = 10, subarrays = 2
- Add 8: current = 18 > 15 → new subarray, current = 8, subarrays = 3
- Total = 3 > k = 2 → NOT FEASIBLE
- left = 16
Step 4: Iteration 3: mid = (16 + 20) / 2 = 18
- Check feasible(18):
- Add 7: current = 7, Add 2: current = 9, Add 5: current = 14
- Add 10: current = 24 > 18 → new subarray, current = 10, subarrays = 2
- Add 8: current = 18 ≤ 18 ✓
- Total = 2 ≤ 2 → FEASIBLE
- result = 18, right = 17
Step 5: Iteration 4: mid = (16 + 17) / 2 = 16
- Check feasible(16):
- Add 7: 7, Add 2: 9, Add 5: 14
- Add 10: 24 > 16 → new, current = 10, subarrays = 2
- Add 8: 18 > 16 → new, current = 8, subarrays = 3
- Total = 3 > 2 → NOT FEASIBLE
- left = 17
Step 6: Iteration 5: mid = (17 + 17) / 2 = 17
- Check feasible(17):
- Add 7: 7, Add 2: 9, Add 5: 14
- Add 10: 24 > 17 → new, current = 10, subarrays = 2
- Add 8: 18 > 17 → new, current = 8, subarrays = 3
- Total = 3 > 2 → NOT FEASIBLE
- left = 18
Step 7: Now left = 18 > right = 17. Binary search ends.
Result: result = 18. The minimum possible largest sum is 18.
Binary Search on Answer — Finding Minimum Feasible Max Sum — Watch how binary search narrows the range of possible answers. For each candidate max sum, a greedy scan determines if the array can be split into ≤ k subarrays.
Algorithm
- Set binary search bounds:
left = max(nums),right = sum(nums). - While
left ≤ right:- Compute
mid = (left + right) / 2. - Run the greedy feasibility check with
max_sum = mid:- Initialize
current_sum = 0,subarrays = 1. - For each element in
nums:- If
current_sum + element > mid, start a new subarray:current_sum = element,subarrays += 1. - Otherwise,
current_sum += element.
- If
- If
subarrays ≤ k,midis feasible.
- Initialize
- If feasible: record
result = mid, search left half (right = mid - 1). - If not feasible: search right half (
left = mid + 1).
- Compute
- Return
result.
Code
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int left = *max_element(nums.begin(), nums.end());
long long right = accumulate(nums.begin(), nums.end(), 0LL);
int result = right;
while (left <= right) {
long long mid = left + (right - left) / 2;
if (canSplit(nums, k, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
private:
bool canSplit(vector<int>& nums, int k, long long maxSum) {
long long currentSum = 0;
int subarrays = 1;
for (int num : nums) {
if (currentSum + num > maxSum) {
currentSum = num;
subarrays++;
} else {
currentSum += num;
}
}
return subarrays <= k;
}
};class Solution:
def splitArray(self, nums: list[int], k: int) -> int:
def can_split(max_sum: int) -> bool:
current_sum = 0
subarrays = 1
for num in nums:
if current_sum + num > max_sum:
current_sum = num
subarrays += 1
else:
current_sum += num
return subarrays <= k
left, right = max(nums), sum(nums)
result = right
while left <= right:
mid = (left + right) // 2
if can_split(mid):
result = mid
right = mid - 1
else:
left = mid + 1
return resultclass Solution {
public int splitArray(int[] nums, int k) {
int left = 0;
long right = 0;
for (int num : nums) {
left = Math.max(left, num);
right += num;
}
long result = right;
while (left <= right) {
long mid = left + (right - left) / 2;
if (canSplit(nums, k, mid)) {
result = mid;
right = mid - 1;
} else {
left = (int)(mid + 1);
}
}
return (int) result;
}
private boolean canSplit(int[] nums, int k, long maxSum) {
long currentSum = 0;
int subarrays = 1;
for (int num : nums) {
if (currentSum + num > maxSum) {
currentSum = num;
subarrays++;
} else {
currentSum += num;
}
}
return subarrays <= k;
}
}Complexity Analysis
Time Complexity: O(n × log(S)) where S = sum(nums) - max(nums).
The binary search runs for O(log S) iterations, since the search range is [max(nums), sum(nums)]. With nums[i] ≤ 10^6 and n ≤ 1000, the total sum is at most 10^9, so log₂(10^9) ≈ 30 iterations. Each iteration does a linear O(n) scan. Total: about 1000 × 30 = 30,000 operations — extremely efficient.
Compare this with the DP approach's O(n² × k) = 1000² × 50 = 50,000,000 operations. The binary search approach is roughly 1,600 times faster.
Space Complexity: O(1). We use only a handful of variables. No additional data structures that scale with input size.