AlgoViz
HomeBinary Search

Split Array — Largest Sum

Hard

Same as book allocation

In simple words

Guess a max piece-sum; if you can split into few enough pieces try smaller, otherwise bigger.

The idea

Minimize the largest subarray sum when splitting into k parts — a bigger cap needs fewer parts, so binary search the smallest feasible cap.

5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
candidates11

Step 1 of 7. Brute force: try every sum-limit until the array splits into 2 parts. Values: 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. candidates 11.

1/7
Brute force
timeO(sum·n)spaceO(1)

Try every limit.

1let best = -1;2for (let cap = maxNum; cap <= sum && best < 0; cap++)3  if (partsNeeded(cap) <= k) best = cap;4return best;

Input

array
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Memory

try
—
candidates
11
limit
—

Output

limit
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [7, 2, 5, 10, 8], k = 2
Output:
18
Explanation:
Split into [7,2,5] and [10,8]; the larger sum, 18, is smallest possible.

Example 2

Input:
nums = [1, 2, 3, 4, 5], k = 2
Output:
9
Explanation:
[1,2,3] and [4,5] give a max part of 9.

Example 3

Input:
nums = [1, 4, 4], k = 3
Output:
4
Explanation:
Each element alone → largest part is 4.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.