Show problems as
Classic problem #410HardArrayBinary SearchDynamic ProgrammingGreedyPrefix Sum

Split Array Largest Sum

Real-world version: Balanced Truckloads
Tracked in this browser only
Read Split Array Largest Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstRange Search · Binary Search, animated step by step

Parcels are queued along a loading bay in one fixed line, and their masses are the integer array weights. A fleet of trucks vehicles is waiting at the far end.

The crew works front to back and never reorders the queue, so each vehicle is handed one unbroken run of neighbouring parcels. Every parcel is loaded, no run overlaps another, and no vehicle may drive off empty. A vehicle's load is the total mass of the run it received.

The shift only ends when the most heavily laden vehicle has finished its route, so the crew wants the biggest of the trucks loads to come out as small as it possibly can. Report the mass of that heaviest load under the best possible cut.

Examples

Example 1

Input
weights = [4, 9, 3, 12, 6, 1], trucks = 3
Output
15

Cutting the line into 4 9 | 3 12 | 6 1 gives loads of 13, 15 and 7, and no other set of two cuts pushes the biggest load below 15.

Example 2

Input
weights = [2, 3, 4, 5], trucks = 4
Output
5

There are exactly as many vehicles as parcels, so each vehicle carries a single parcel and the heaviest load is the heaviest parcel.

Example 3

Input
weights = [8, 1, 1, 1], trucks = 1
Output
11

With one vehicle the whole queue travels together, so the answer is the total mass.

Constraints

  • 1 <= weights.length <= 1000
  • 0 <= weights[i] <= 10^6
  • 1 <= trucks <= min(50, weights.length)
  • Each run of parcels must be contiguous and the queue order is fixed

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_heaviest_load(weights: list[int], trucks: int) -> int:
Java
public int minHeaviestLoad(int[] weights, int trucks)

More on the same topics