.png)
Split Array Largest Sum
Problem Statement
You are given an integer array nums and an integer k.
Split the array into k or fewer non-empty continuous subarrays such that the largest sum among these subarrays is minimized.
Return the minimum possible largest subarray sum.
Example
Input
nums = [7,2,5,10,8]
k = 2
Output
18
Explanation
Possible splits:
- [7,2,5] and [10,8] → max sum = 18 ✅
- [7,2], [5,10,8] → max sum = 23 ❌
Minimum possible largest sum = 18
Why This Problem Is Important
- Classic Binary Search on Answer
- Asked in Google, Amazon, Microsoft
- Tests:
- Greedy feasibility check
- Binary search intuition
- Foundation for:
- Load balancing
- Partition DP
- Scheduling problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force Partitioning | Exponential | O(k) |
| Approach 2 | Dynamic Programming | O(n²·k) | O(n·k) |
| Approach 3 | Binary Search + Greedy (Optimal) | O(n log S) | O(1) |
S = sum(nums)
Approach 1: Brute Force (All Possible Splits)
Idea
- Try all ways to split array into ≤ k parts
- Compute maximum subarray sum for each split
- Take minimum among all
Time & Space
- Time: Exponential
- Space: O(k)
Only for understanding, not for interviews.
Python (Conceptual)
def dfs(i, k, curr_sum, max_sum):
if i == len(nums):
if k == 0:
return max_sum
return float('inf')
if k == 0:
return float('inf')
# continue current subarray
take = dfs(i+1, k, curr_sum + nums[i],
max(max_sum, curr_sum + nums[i]))
# start new subarray
split = dfs(i+1, k-1, nums[i],
max(max_sum, nums[i]))
return min(take, split)
nums = [7,2,5,10,8]
print(dfs(1, 2, nums[0], nums[0]))
Output
18
Approach 2: Dynamic Programming
Idea
dp[i][j] = minimum largest subarray sum when splitting first i elements into j subarrays
Transition:
dp[i][j] = min over x < i of
max(dp[x][j-1], sum(x → i-1))
Time & Space
- Time: O(n² · k)
- Space: O(n · k)
Python
import math
nums = [7,2,5,10,8]
k = 2
n = len(nums)
prefix = [0]*(n+1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i]
dp = [[math.inf]*(k+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
for j in range(1, k+1):
for x in range(i):
dp[i][j] = min(
dp[i][j],
max(dp[x][j-1], prefix[i] - prefix[x])
)
print(dp[n][k])
C++
#include
using namespace std;
int main() {
vector nums = {7,2,5,10,8};
int k = 2, n = nums.size();
vector prefix(n+1, 0);
for(int i=0;i> dp(n+1, vector(k+1, INT_MAX));
dp[0][0] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
for(int x=0;xJava
import java.util.*;
class SplitArray {
public static void main(String[] args) {
int[] nums = {7,2,5,10,8};
int k = 2, n = nums.length;
int[] prefix = new int[n+1];
for(int i=0;iOutput
18
Approach 3: Binary Search on Answer (Optimal)
Idea
- Answer lies between:
- min = max(nums)
- max = sum(nums)
- Binary search this range
- Check feasibility using greedy
Feasibility Check
- Keep adding elements
- If sum > mid → create new subarray
- Count subarrays
Time & Space
- Time: O(n log S)
- Space: O(1)
Python
def canSplit(maxSum):
curr = 0
pieces = 1
for x in nums:
if curr + x > maxSum:
pieces += 1
curr = x
else:
curr += x
return pieces <= k
nums = [7,2,5,10,8]
k = 2
low, high = max(nums), sum(nums)
while low < high:
mid = (low + high) // 2
if canSplit(mid):
high = mid
else:
low = mid + 1
print(low)
C++
#include
using namespace std;
bool canSplit(vector& nums, int k, int maxSum){
int curr = 0, pieces = 1;
for(int x : nums){
if(curr + x > maxSum){
pieces++;
curr = x;
} else curr += x;
}
return pieces <= k;
}
int main(){
vector nums = {7,2,5,10,8};
int k = 2;
int low = *max_element(nums.begin(), nums.end());
int high = accumulate(nums.begin(), nums.end(), 0);
while(low < high){
int mid = low + (high-low)/2;
if(canSplit(nums, k, mid))
high = mid;
else
low = mid + 1;
}
cout << low;
}
Java
class SplitArray {
static boolean canSplit(int[] nums, int k, int maxSum){
int curr = 0, pieces = 1;
for(int x : nums){
if(curr + x > maxSum){
pieces++;
curr = x;
} else curr += x;
}
return pieces <= k;
}
public static void main(String[] args){
int[] nums = {7,2,5,10,8};
int k = 2;
int low = 0, high = 0;
for(int x : nums){
low = Math.max(low, x);
high += x;
}
while(low < high){
int mid = low + (high-low)/2;
if(canSplit(nums, k, mid))
high = mid;
else
low = mid + 1;
}
System.out.println(low);
}
}
JavaScript
function canSplit(nums, k, maxSum){
let curr = 0, pieces = 1;
for(let x of nums){
if(curr + x > maxSum){
pieces++;
curr = x;
} else curr += x;
}
return pieces <= k;
}
let nums = [7,2,5,10,8];
let k = 2;
let low = Math.max(...nums);
let high = nums.reduce((a,b)=>a+b,0);
while(low < high){
let mid = Math.floor((low + high)/2);
if(canSplit(nums, k, mid))
high = mid;
else
low = mid + 1;
}
console.log(low);
C#
using System;
class Program {
static bool CanSplit(int[] nums, int k, int maxSum){
int curr = 0, pieces = 1;
foreach(int x in nums){
if(curr + x > maxSum){
pieces++;
curr = x;
} else curr += x;
}
return pieces <= k;
}
static void Main(){
int[] nums = {7,2,5,10,8};
int k = 2;
int low = 0, high = 0;
foreach(int x in nums){
low = Math.Max(low, x);
high += x;
}
while(low < high){
int mid = low + (high-low)/2;
if(CanSplit(nums, k, mid))
high = mid;
else
low = mid + 1;
}
Console.WriteLine(low);
}
}
Output
18
Final Summary
- Brute Force: Learning only
- DP: Clear logic, slower
- Binary Search + Greedy: BEST & INTERVIEW FAVORITE
Key Pattern:
When asked to minimize the maximum → Binary Search the answer
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
