Divide Chocolate

Hard

Given an array nums of chunk sweetness values and an integer target (the number of cuts), you split the bar into target + 1 contiguous pieces and keep the piece with the smallest total sweetness. Return the maximum total sweetness of the piece you can guarantee for yourself.

Example 1

Input:  nums = [1,2,3,4,5,6,7,8,9], target = 5
Output: 6

Example 2

Input:  nums = [5,6,7,8,9,1,2,3,4], target = 8
Output: 1

Example 3

Input:  nums = [1,2,2,1,2,2,1,2,2], target = 2
Output: 5

Constraints

• 0 <= target < nums.length <= 10^4
• 1 <= nums[i] <= 10^5