Hints on subarray minmax problem?

Правка en1, от EugeneJudo, 2021-08-11 19:37:31

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 maximum sum subarray, 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский EugeneJudo 2021-08-11 19:38:16 19
en1 Английский EugeneJudo 2021-08-11 19:37:31 861 Initial revision (published)