Divide Chocolate

Intuition

Guessing a target sweetness x for the weakest piece has a monotonic structure: if you can carve out k + 1 pieces each worth at least x, then any smaller target is also achievable. That lets us binary search on x. The feasibility test is greedy: walk left to right accumulating sweetness, and every time the running total reaches x, seal a piece and reset. If the greedy scan produces enough pieces, the target is reachable, so we push for a higher target; otherwise we lower it.

Algorithm walkthrough

1. 1Set lo to the smallest chunk and hi to the total sweetness divided by (k + 1), the best a minimum piece could ever be.
2. 2Choose the upper mid of the window as the candidate minimum sweetness x.
3. 3Greedily accumulate chunks; whenever the running sum reaches x, count a completed piece and reset the sum.
4. 4If the count of completed pieces is at least k + 1, the target is feasible, so raise lo to mid; otherwise lower hi to mid - 1.
5. 5When the window collapses, lo holds the maximum achievable minimum sweetness.

Implementation

from typing import List

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def can_cut(x: int) -> bool:
            pieces = cur = 0
            for s in sweetness:
                cur += s
                if cur >= x:
                    pieces += 1
                    cur = 0
            return pieces >= k + 1
        lo, hi = min(sweetness), sum(sweetness) // (k + 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if can_cut(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo