I have a question that I can't understand.
Solution said we should iterate x which is the number of subarrays with maximum sums that we will use. But what will we do if we have two subarrays with equal sums?
for example
4 3
-11 16 -11 -1
We will choose 16
for sure. Then we have two options. One is -11 16
and 16 -11 -1
, the other is 16 -11
and -11 16 -11 -1
. The first one has a better answer.
izban proved that if some pair of subsegments have same sum, it doesn't matter when we choose first $$$k - n$$$ subarrays. But his proof is not correct when we choose $$$> k - n$$$ subarrays.