Maximize 5-independent gifts on a path Question: Assume there are $n$ distinct gifts on the real line. Their
positions are $\{x_1, ..., x_n\}$ and each of them has an individual
value $p_i$.
Now you can choose a subset of them such that any two gifts in your
choice are at a distance more than 5. What’s the maximum total value you
can get? Design an algorithm to solve this problem, analyze the running
time and prove the correctness.
You can assume the gifts are given in order of their locations, i.e.,
$x_1 &lt; x_2 &lt; ... &lt; x_n$.
I have tried memoization and breaking down the problem into smaller
steps but I am not sure what this specific sub case would look
like.
Here is some pseudocode that illustrates the recursive idea.

If you choose to take this element, then you have to skip ahead 6 steps.
Otherwise you skip this element and go to the next.

def solve(array, index):
    if index &gt;= len(array):
        return 0
    this_one       = array[index]             # the value x_i
    opt_five_steps = solve(array, index + 6)  # the opt of array[i+6:]
    opt_successor  = solve(array, index + 1)  # the opt of array[i+1:]
    return max(this_one + opt_five_steps,
               opt_successor)

Clearly, this can be turned into a DP algorithm, or memoized as is.