You have a chocolate bar made up of several chunks, and each chunk has a certain sweetness, given in an array called sweetness. You want to share the chocolate with k friends. To do this, you’ll make k cuts to divide the bar into k + 1 parts. Each part will consist of consecutive chunks.
Being a kind person, you’ll take the piece with the minimum total sweetness and give the other pieces to your friends.
Your task is to find the maximum total sweetness of the piece you will receive if you cut the chocolate bar optimally.
Constraints:
k sweetness.length
sweetness[i]
As we have a chocolate bar made of several chunks, each with its own sweetness value, dividing the chocolate evenly won’t ensure that we get the chocolate part with the maximum possible minimum sweetness. The next natural thought for solving this problem is to try to cut the chocolate in different ways and find out the one that gives the desired result. But it becomes very inefficient when the chocolate bar is long. There are just too many possible combinations of where to cut, and checking each one would take too much time.
So, instead of guessing exactly where to cut, we flip the problem and ask: What is the largest minimum sweetness we can guarantee for ourselves if we divide the chocolate bar into k + 1 pieces?
The ...
You have a chocolate bar made up of several chunks, and each chunk has a certain sweetness, given in an array called sweetness. You want to share the chocolate with k friends. To do this, you’ll make k cuts to divide the bar into k + 1 parts. Each part will consist of consecutive chunks.
Being a kind person, you’ll take the piece with the minimum total sweetness and give the other pieces to your friends.
Your task is to find the maximum total sweetness of the piece you will receive if you cut the chocolate bar optimally.
Constraints:
k sweetness.length
sweetness[i]
As we have a chocolate bar made of several chunks, each with its own sweetness value, dividing the chocolate evenly won’t ensure that we get the chocolate part with the maximum possible minimum sweetness. The next natural thought for solving this problem is to try to cut the chocolate in different ways and find out the one that gives the desired result. But it becomes very inefficient when the chocolate bar is long. There are just too many possible combinations of where to cut, and checking each one would take too much time.
So, instead of guessing exactly where to cut, we flip the problem and ask: What is the largest minimum sweetness we can guarantee for ourselves if we divide the chocolate bar into k + 1 pieces?
The ...