1231. Divide Chocolate
Problem
Divide a chocolate bar into k+1 pieces and maximize the minimum total sweetness of any piece.
Given an integer array chocolate representing a chocolate bar (row of chocolate squares) and an integer k, you want to divide the chocolate bar into k+1 pieces by making k cuts. Each piece has a total sweetness equal to the sum of chocolate squares in that piece.
Your goal is to maximize the minimum total sweetness among all pieces. Return this maximum possible minimum value.
Examples
Input: [[1,2,3,4,5,6,7,8,9],5]
Output: 6
Input: [[1,2,4,4,6],3]
Output: 3
Hints
Use binary search on the answer: try a target minimum sum and check if you can make k+1 pieces with at least that sum each.
For a given minimum, count how many pieces you can get by greedily taking as many squares as possible.
Binary search between min(chocolate) and sum(chocolate).
Related Problems
1231. Divide Chocolate
Divide a chocolate bar into k+1 pieces and maximize the minimum total sweetness of any piece.