Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?
Without loss of generality, assume $p_i&gt; 0$. Otherwise we can set all $x_i=0$ where $p_i\le 0$ and consider the separated sequences by these $i$'s respectively.

Let $P(k)$ and $Q(k)$ be the highest possible points we can get for $p_1,\ldots,p_k$ where $x_{k-1}x_k=11$ and where $x_{k-1}x_k\neq 11$ respectively.

If the last two bits are $11$, $x_{k-2}$ must be $0$, and there are no constraint for $x_1,\ldots,x_{k-3}$, hence
$$P(k)=p_{k-1}+p_k+\max\{P(k-3),Q(k-3)\}.$$

If the last two bits are not $11$, there are two cases: $01$ or $10$. Note to get the highest points, the last two bits cannot be $00$.


If the last two bits are $01$, there is no constraint for previous bits, the highest possible points are $p_k+\max\{P(k-2),Q(k-2)\}$.
If the last two bits are $10$, then $x_{k-3}x_{k-2}\neq 11$, the highest possible points are $p_{k-1}+Q(k-2)$.


So

$$Q(k)=\max\left\{p_k+\max\{P(k-2),Q(k-2)\},p_{k-1}+Q(k-2)\right\}.$$

Use the two recursion formulas above, you can compute the final result $\max\{P(n),Q(n)\}$.