Try all permutations of array

In this problem it must be negative values in the array so, It is important to know that if you can achieve largest subsegment sum to be X then you can achieve largest subsegment sum equals to Y where Y >= X.

So you can make 2 vectors, first holding positive values and the other holding negative values and make binary search on the maximum subsegment sum.

To know if you can rearrange the elements so that the maximum subsegment sum is at most mid you can iterate over the positive values and start with variable sum is equal to 0 then you can choose to put positive value or negative value according to the state (the current maximum subsegment sum).

You can see this problem, It is similar to your idea, if the link dose not open, make sure to join here. and this is my solution (code).