We will do Dynamic Programming with the following two keys, choosing the terms from front to back.

• The number of terms already chosen
• The set of elements already used

However, there are \(2^n\) possible sets of used elements, so we need to do better than maintaining them naively.

When the first \(i\) terms are chosen, there is no way to choose the rest to satisfy the conditions if the following is not satisfied.

• All elements less than or equal to \(i-d\) are used.
• No elements greater than or equal to \(i+d+2\) are used.

Thus, it is enough to remember, for each \(i\), whether each number between \(i-d+1\) and \(i+d+1\) is used. There are only \(2^{2d+1}\) sets to remember, making the size of the table of the dynamic programming \(O(4^dn)\). There are \(d\) transitions for each state, so the complexity is \(O(4^ddn)\).

Sample Implementation in C++