.-.-.-'s blog

Rearrange array elements to minimize the SUM of the subsegment with the largest sum
By .-.-.-, history, 5 hours ago, In English

Any ideas?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it -10 Vote: I do not like it

Try all permutations of array

→ Reply
»
4 hours ago, # |
  Vote: I like it +11 Vote: I do not like it

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).

→ Reply
  • »
    »
    63 minutes ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    6

    1 3 7 8 -17 -1

    breaks it

    your code would make 1 3 -17 7 -1 8 at mid = 9 which this doesnt satify

    however it can still work with mid = 9

    1 8 -17 3 -1 7

    ok i just read the other problem the differenece is you can still shuffle A and B here which screws up your algo

    → Reply