# Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?

The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So the total points is $\sum_{i=1}^{n}x_ip_i$. Our rule is that we cannot have three consecutive $1$'s, and we want to know what is highest possible points we can get from a length-$n$ sequence.

I propose an algorithm, but I find examples that leads to non-optimal solution. My algorithm basically goes as follows: let $P(k-1)$ be the highest possible points we can get for the length-$(k-1)$ sequence, with points $p_1,\ldots,p_{k-1}$, and it corresponds to an optimal length-$(k-1)$ sequence $s_{k-1}$, then I add an $1$ at $k_{th}$ position if it's possible to do so. If it is not possible to add $1$, then the previous 3 terms must be $011$. Then I compare $p_k,p_{k-1}$ and $p_{k-2}$, and put two $1$'s at two positions with the highest points, and put $0$ on remaining position. Hence I get $P(k)$, and $P(n)$ is computed by computing each $P(i)$.

However, consider the example of $n=4$, and $p_1=1,p_2=3,p_3=2,p_4=4$, this algorithm will produce $0101$, and $P(4)=7$, while $1101$ will have $8$ points.

Anyone has a suggestions on what is a true algorithm for this problem? Thanks!

Without loss of generality, assume $p_i> 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)\}$.