Adjust every $x_i\in\{0,1\}$. Then we get some paragraph of 0 and 1. We can adjust 1 such that every 1 contain at most two 1s. We can adjust 0 such that every paragraph of zero contains and even number of 0s. Then the maximum is $\lfloor\frac{n}2\rfloor$

smy2012 wrote: Adjust every $x_i\in\{0,1\}$. Then we get some paragraph of 0 and 1. We can adjust 1 such that every 1 contain at most two 1s. We can adjust 0 such that every paragraph of zero contains and even number of 0s. Then the maximum is $\lfloor\frac{n}2\rfloor$ Let $P = - x_1x_2 + x_2x_3 - x_3x_4 + \ldots + x_{2n}x_1 $ be the expression we want to maximize. Since $P$ is linear in each of the $x_i$, hence the maximum occurs when $x_i \in \{ 0, 1 \}$. __Hint:__ $P = x_1 (x_{2n} - x_2) + x_3 (x_2 - x_4) + \ldots + x_{2n-1} (x_{2n-2} - x_{2n})$. Let $a_i = x_{2(i-1)} - x_{2i}$ for $ i = 1$ to $n$. Clearly, $a_i \in \{ 1, 0, -1 \}$ and $\sum a_i = 0$. __Hint:__ $ P \leq $ the number of $a_i$ which is equal to 1. Hence $ P \leq \lfloor \frac{n}{2} \rfloor$. Can equality hold?