Notice that if $$$s$$$ starts with a $$$1$$$ we must move the entire string $$$s$$$ to $$$t$$$ at some point. Also Notice that if we perform the operation, the total number of occurrences of $$$01$$$ and $$$10$$$ across both strings can only decrease by one. This gives us an upper bound on the answer being the number of occurrences of $$$01$$$ and $$$10$$$ in $$$s$$$ adding one to this if it starts with the character $$$1$$$.

Now the following construction uses the same number of moves as the upper bound (thus showing it is the minimum number of moves): If $$$s$$$ begins with $$$1$$$ then select the entire string $$$s$$$ and move it to $$$t$$$. Then repeatedly find the first character in $$$s$$$ or $$$t$$$ which is not equal to the character before it (note under this construction such an index can only exist in one string at a time) and selected the suffix starting from this character and move it to the other string. During this construction some prefix of $$$s$$$ will contain $$$0$$$s and some prefix of $$$t$$$ will contain $$$0$$$s, so after each move the total number of $$$01$$$ and $$$10$$$ will decrease.

So the answer to this problem will be the number of $$$01$$$ and $$$10$$$ in $$$s$$$ adding one to the answer if it starts with $$$1$$$.

The first thing to notice is that if we remove an element from $$$a$$$ then our score will never increase. Because removing one element will cause $$$|a|$$$ to decrease by $$$1$$$ and $$$\mathrm{distinct}(a)$$$ will decrease by at most $$$1$$$ and so the $$$|a|$$$ — $$$\mathrm{distinct}(a)$$$ will never increase. This means that we should be trying to removing the longest subarray which does not decrease our score.

We can see that removing any element which only occurs once in $$$a$$$ will never decrease our score, and that removing any element which occurs more than once will always decrease our score. Thus we should try to find the longest subarray of elements which only have $$$1$$$ occurrence in $$$a$$$ and this will be the answer. This can be calculated with a single loop in $$$O(n)$$$.

First see that at any point we should either remove the leftmost positive element or the rightmost negative element, as if we were to take a positive element that is not the leftmost one we could have just taken the leftmost one first and had a higher score. Now if you do either of these moves some number of times you will always take some prefix of positive numbers and then the remaining suffix of negative numbers, and so to calculate the answer we only need to check all $$$n + 1$$$ ways to split the array into a prefix and suffix and take the maximum across them all.