hardBinary SearchPure DSA~40 min
Split Workload Into K Parts Minimizing The Heaviest
A sequence of jobs (with fixed weights, processed in order) must be divided into k contiguous shards assigned to k workers. Minimize the load of the busiest worker — the maximum shard sum.
Problem
Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays so the largest subarray sum is minimized. Return that minimized largest sum.
Input
An integer array nums and an integer k.
Output
The minimized maximum subarray sum.
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ nums[i] ≤ 1e6
- 1 ≤ k ≤ n
Examples
Example 1
Input
nums=[7,2,5,10,8] k=2
Output
18
Split [7,2,5] and [10,8] → max(14,18)=18, the best possible.
Example 2
Input
nums=[1,2,3,4,5] k=2
Output
9
[1,2,3] and [4,5] → max(6,9)=9.