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.