A binary array is an array where all elements are either $$$0$$$ or $$$1$$$.
For any binary array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, we can figure out the corresponding unique array $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$ that satisfies $$$b_1 = a_1$$$ and $$$b_i = a_i \oplus a_{i - 1}$$$ for any $$$2 \le i \le n$$$, where $$$\oplus$$$ denotes XOR operation. Then count the number of $$$1$$$-s in array $$$a$$$, count the number of $$$1$$$-s in array $$$b$$$, and find the minimum of them as the “score” of array $$$a$$$.
For example, provided $$$a = [1, 0, 1, 1, 0, 0]$$$, then $$$b = [1, 1, 1, 0, 1, 0]$$$. The number of $$$1$$$-s in array $$$a$$$ is $$$3$$$, the number of $$$1$$$-s in array $$$b$$$ is $$$4$$$, and the minimum of them is $$$3$$$, so the “score” of array $$$a = [1, 0, 1, 1, 0, 0]$$$ is $$$3$$$.
For any given $$$n$$$, what is the maximum “score” of array $$$a$$$ among all possible arrays $$$a$$$? And how to construct a possible array $$$a$$$?
I believe the answer is $$$\lceil{\frac{n}{2}}\rceil$$$
I don’t believe so. For $$$n = 4$$$, the answer is not $$$\big\lceil \frac n 2 \big\rceil = 2$$$ but $$$3$$$, because we can construct an array $$$a = [1, 0, 1, 1]$$$, where $$$b = [1, 1, 1, 0]$$$.
My bad! Well now we have a lower bound for the answer. Also notice something: for the array $$$a = [1, 0, 1, 0, \dots], b = [1, 1, 1, 1, \dots]$$$ If we replace any 0 with a 1 in the array $$$a$$$, it will add 1 1 to the array $$$a$$$ and remove 2 (or 1) 1 from the array $$$b$$$. Hope that helps!
But what if we don’t make the values at odd indices $$$1$$$? That is, what if we don’t form our array like $$$a = [1, \texttt{X}, 1, \texttt{X}, \ldots]$$$? Such as, $$$a = [1, 1, 0, 0, 1, 1, 0, 0, \ldots]$$$ — just like when we move some $$$1$$$-valued elements to other positions.
Ww can get something around $$$2n/3$$$ with $$$a = [1, 1, 0, 1, 1, 0,\dots]$$$ and $$$b = [1, 0, 1, 1, 0, 1,\dots]$$$
I bruteforced all possible sequences for $$$1 \le n \le 12$$$ and it looks like the maximum score is always $$$\lfloor \frac{2n+1}{3} \rfloor$$$. It is not hard to see that this score can be obtained by using the pattern $$$[1,0,1,1,0,1,1,0,1,\dots]$$$. Unfortunately I don't know how to prove these claims.
So am I hahaha
Consider having $$$x$$$ ones in array $$$a$$$.
First assume that $$$x \lt \frac{n}{2}$$$. Then, we can make a prefix of alternating zeros and ones, followed by a bunch of zeros. Then, array $$$b$$$ has something like $$$2x$$$ ones. Then the score is $$$\min(x,2x)=x$$$ (which is less than half $$$n$$$).
Now let's try $$$x \gt \frac{n}{2}$$$. Now, we can make $$$a$$$ have an alternating prefix and a suffix full of ones. The length of the alternating prefix is approximately $$$2n-2x$$$, so the score is $$$\min(x, 2n-2x)$$$, which is maximized when $$$x=2n-2x$$$ therefore $$$\text{score}=x=2n/3$$$.
I'm not being precise with my rounding and so on but you get the idea. Also, i didn't prove that this construction is optimal but it's very intuitive that the amount of ones in $$$b$$$ is maximized when we construct $$$a$$$ as described (again, sorry for lack of proof)
EDIT:
We can prove optimality by first proving an upper bound and then showing that my construction achieves it.
If there are more zeros than ones in $$$a$$$, you can only have at most $$$2x$$$ ones in $$$b$$$, because that's the amount of adjacent positions there can be next to a one.
On the other hand, if there are more ones than zeros in $$$a$$$, we are limited by the number of zeros, which is $$$n-x$$$, so there can be at most $$$2(n-x)$$$ ones in $$$b$$$. (same argument as above)
Note that the proposed construction reaches both bounds (trivial), so it must be optimal.