Divide Chocolate

Problem A chocolate bar has n contiguous chunks with sweetness values. Make k cuts to produce k+1 contiguous pieces; you keep the piece with the minimum total sweetness. Maximize the sweetness of the piece you keep.

Input / Output

• Input: int array sweetness, int k.
• Output: the maximum achievable minimum-piece total.

Constraints

• 0 <= k < n <= 10^4; values up to 10^5.

Example

• sweetness = [1,2,3,4,5,6,7,8,9], k = 5 → 6 (pieces [1,2,3], [4,5], [6], [7], [8], [9]).