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

Question

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!

Answer 1

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)\}$.