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