# 1231. Divide Chocolate

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array `sweetness`.

You want to share the chocolate with your `K` friends so you start cutting the chocolate bar into `K+1` pieces using `K` cuts, each piece consists of some **consecutive** chunks.

Being generous, you will eat the piece with the **minimum total sweetness** and give the other pieces to your friends.

Find the **maximum total sweetness** of the piece you can get by cutting the chocolate bar optimally.

**Example 1:**

```
Input: sweetness = [1,2,3,4,5,6,7,8,9], K = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]
```

**Example 2:**

```
Input: sweetness = [5,6,7,8,9,1,2,3,4], K = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.
```

**Example 3:**

```
Input: sweetness = [1,2,2,1,2,2,1,2,2], K = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]
```

**Constraints:**

* `0 <= K < sweetness.length <= 10^4`
* `1 <= sweetness[i] <= 10^5`

```cpp
// Binary Search + Greedy
int maximizeSweetness(vector<int>& sweetness, int K) { // time: O(nlogn); space: O(1)
    int left = 1, right = accumulate(sweetness.begin(), sweetness.end(), 0) / (K + 1));
    while (left < right) {
        int targetSum = left + (right - left + 1) / 2;
        int curSum = 0, cut = 0;
        for (const int& num : sweetness) {
            curSum += num;
            if (curSum >= targetSum) {
                curSum = 0;
                if (++cut > K) break;
            }
        }
        if (cut > K) left = targetSum;
        else right = targetSum - 1;
    }
    return right;
}
```

{% content-ref url="410.-split-array-largest-sum" %}
[410.-split-array-largest-sum](410.-split-array-largest-sum)
{% endcontent-ref %}

{% content-ref url="774.-minimize-max-distance-to-gas-station" %}
[774.-minimize-max-distance-to-gas-station](774.-minimize-max-distance-to-gas-station)
{% endcontent-ref %}

{% content-ref url="875.-koko-eating-bananas" %}
[875.-koko-eating-bananas](875.-koko-eating-bananas)
{% endcontent-ref %}

{% content-ref url="1011.-capacity-to-ship-packages-within-d-days" %}
[1011.-capacity-to-ship-packages-within-d-days](1011.-capacity-to-ship-packages-within-d-days)
{% endcontent-ref %}
