When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

pravsin's blog

By pravsin, history, 6 years ago, In English

Hi, I am trying to understand the solution for below question. The explanation for good but I don't understand the logic behind it. Can someone please explain the logic behind the given solution.

https://stackoverflow.com/questions/37240178/pick-numbers-to-maximize-interval

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Define dp(i, j) = Maximum minimum distance you can achieve if you choose i numbers, and the last number you chose was in index j.

When calculating dp(i, j), you can brute-force all positions k < j, and try taking the number at index k. Then choose i - 1 numbers from the rest and maximize distance, which is just dp(i - 1, k), when you have chosen i - 1 numbers and the last number you chose was at index k.

So the transition is -
dp(i, j) = max1 ≤ k < p{min(dp(i - 1, k), aj - ak)}

Then the answer to the problem will be maximum of dp(N, N), dp(N, N + 1), ..., dp(N, n).
Time Complexity O(n3).

[Notice that the answer posted in stack-overflow has two max in the transition, but the second one should be min.]