jlsxly's blog

Dp or greedy?
By jlsxly, history, 4 years ago, In English

Here is a sequence with n integers in it. Each of the integers is 1 or -1.

You have to rearrange the sequence, to get the maximum interval sum to be MINIMUM.

I would like to know how many arrangements there are.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, hide # |
← Rev. 2  
Vote: I like it -23 Vote: I do not like it

Two important observations in this problem:

  1. If the sum of all elements is 1 or smaller, and at least one 1 element exists, there is always a way to make the maximum interval sum to 1.
  2. If the sum of all elements is greater than 1, or all elements are -1, then always, the maximum interval sum is constant.

I believe you will be able to find a solution, given these observations.

→ Reply