I've spent the past few days thinking over https://cses.fi/problemset/task/1085/ without much progress. Looking for a hint to go in the right direction.
One failed method I implemented was to greedily always split the current max sum subarray in two, keeping track of ranges and sums with a priority queue. If it ever hit a single element, then it was clearly done since we can't do better than that, and otherwise output the final max sum. This failed because for instance [111111111]
is best divided as [111|111|111]
whereas my method would yield [1111|111|11]
. My thinking has been that this method may still kind of work by picking the max, combining it with its neighboring regions, and splitting it into 4 instead of 3 subarrays (or fewer in the case that there were fewer neighbors), but this also feels overly complicated.
imagine it like this i gave you k bags with c capacity to hold stuff, but if i gave you more bags, i.e. k + y, you will require bags with c' capacity, c' <= c . vice versa is also true more capacity less bags.
hence you can binary search on capacity c until you are closest to k bags.
BS