Make k Cuts in a Row of Positive Values to Maximize the Smallest Piece Sum
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an array `sweetness` of positive integers describing consecutive chunks of a bar, and an integer `k`. Make exactly `k` cuts to split the bar into `k + 1` non-empty pieces of consecutive chunks. You keep the piece with the smallest total sweetness and give the others away.
Choose the cuts to maximize the total sweetness of the piece you keep, and return that maximum.
### Function Signature
```python
def max_min_piece(sweetness: list[int], k: int) -> int:
```
### Rules
- Every piece is a contiguous, non-empty block of chunks, and every chunk belongs to exactly one piece.
- The value of a way of cutting is the smallest piece total. Return the largest value over all ways of making exactly `k` cuts.
- With `k = 0` there is one piece: the whole bar.
### Constraints
- `0 <= k < len(sweetness) <= 10^4`
- `1 <= sweetness[i] <= 10^5`, so every total is at most `10^9`
### Examples
**Example 1**
```text
Input: sweetness = [5, 1, 4, 2, 8, 3], k = 2
Output: 6
```
Cutting into `[5, 1]`, `[4, 2]` and `[8, 3]` gives totals 6, 6 and 11. No way of cutting makes every piece at least 7.
**Example 2**
```text
Input: sweetness = [3, 3, 3], k = 0
Output: 9
```
**Example 3**
```text
Input: sweetness = [4, 1, 1, 1, 4], k = 4
Output: 1
```
Every chunk becomes its own piece.
Overview: Split an array of positive values into k plus one contiguous pieces so that the smallest piece sum is as large as possible, and return that sum. Tests recognizing a monotone feasibility check, binary search on the answer and greedy partitioning with tight bounds.
You are given an array `sweetness` of positive integers, where `sweetness[i]` is the sweetness of the `i`-th consecutive chunk of a bar, and an integer `k`. Make exactly `k` cuts to split the bar into `k + 1` non-empty pieces, each made of consecutive chunks. You keep the piece with the smallest total sweetness and give the others away.
Choose the cuts to maximize the total sweetness of the piece you keep, and return that maximum.
### Rules
- Every piece is a contiguous, non-empty block of chunks, and every chunk belongs to exactly one piece.
- The value of a way of cutting is the smallest piece total. Return the largest value over all ways of making exactly `k` cuts.
- With `k = 0` there is one piece: the whole bar.
- The answer is a single integer, so when several ways of cutting reach the same maximum the returned value is the same.
### Constraints
- `0 <= k < len(sweetness) <= 10^4`
- `1 <= sweetness[i] <= 10^5`, so every total is at most `10^9`
- Every total, including the answer, is therefore below `2^31 - 1` and fits in a signed 32-bit integer.
### Example 1
```text
Input: sweetness = [5, 1, 4, 2, 8, 3], k = 2
Output: 6
```
Cutting into `[5, 1]`, `[4, 2]` and `[8, 3]` gives totals 6, 6 and 11. No way of cutting makes every piece at least 7.
### Example 2
```text
Input: sweetness = [4, 1, 1, 1, 4], k = 4
Output: 1
```
Every chunk becomes its own piece, so the smallest piece is a single chunk of sweetness 1.
Constraints
- 0 <= k < len(sweetness) <= 10^4
- 1 <= sweetness[i] <= 10^5, so every total is at most 10^9
- Every total, including the answer, is at most 10^9 < 2^31 - 1, so it fits in a signed 32-bit integer
Examples
Input: ([5, 1, 4, 2, 8, 3], 2)
Expected Output: 6
Explanation: Source example 1: [5, 1], [4, 2], [8, 3] give 6, 6, 11; no layout makes every piece at least 7.
Input: ([3, 3, 3], 0)
Expected Output: 9
Explanation: Source example 2: k = 0 keeps the whole bar, total 9.
Hints
- The piece you keep can never be sweeter than the total divided by k + 1, and it is never less sweet than the least sweet single chunk.
- Every chunk must belong to some piece, so a short run of chunks left over at the end of the bar cannot be dropped; it has to join a neighbouring piece.
- Check your reasoning on the two extremes: k = 0 (the whole bar is one piece) and k = len(sweetness) - 1 (every chunk is its own piece).