Shard Rebalance Threshold
A storage operator must split n keys across k shards. Each key i has a size sizes[i]. They want to find the SMALLEST possible value for the largest shard's total size, while keeping shard assignments contiguous (i.e. each shard owns a prefix range of keys).
Problem
Given an integer array sizes of length n and an integer k (k ≤ n), partition sizes into k non-empty contiguous subarrays so that the maximum sum of any subarray is minimised. Return that minimised maximum sum.
Input
Integers n (1 ≤ n ≤ 10^5) and k (1 ≤ k ≤ n), and the array sizes with each in [1, 10^6].
Output
A single integer — the minimised maximum shard total.
Constraints
- 1 ≤ k ≤ n ≤ 100,000
- 1 ≤ sizes[i] ≤ 1,000,000
- Shards must be contiguous prefixes — each shard owns a [l, r] range of indices
- Each shard must be non-empty
Examples
Example 1
Input
sizes = [7, 2, 5, 10, 8], k = 2
Output
18
Best split: [7,2,5] = 14 and [10,8] = 18. Max = 18. Any other 2-cut produces a larger max.
Example 2
Input
sizes = [1, 2, 3, 4, 5], k = 5
Output
5
Every key is its own shard. Max shard sum is 5.