Alternating Series

We need build the lexicographically smallest absolute-value sequence among all good arrays. The annoying-looking “all subarrays” condition is actually pretty tame once the signs are pinned down.

Step 1: The first element

Because adjacent products must be negative, all elements are nonzero and signs alternate.

So $|a_i| \ge 1$ for every $i$.

Can we make $|a_1|=1$? There are two sign choices:

• If $a_1=1$, then $a_2$ must be negative. But the subarray $[a_1,a_2]$ must have positive sum, so $1+a_2>0$. Since $a_2\le -1$, this is impossible.
• If $a_1=-1$, then $a_2$ must be positive, and this can work.

So the lexicographically best possible start is forced:

$$a_1=-1.$$

No drama, just math doing a quick mugging.

Step 2: The signs are forced

Since signs alternate and $a_1$ is negative, the whole sign pattern is forced:

$$-, +, -, +, -, +, \ldots$$

Now we want absolute values as small as possible from left to right.

At every odd position, the value is negative, and the smallest possible absolute value is $1$. So the natural candidate is:

$$a_1=a_3=a_5=\cdots=-1.$$

This is obviously best if it works, because you cannot have absolute value below $1$.

Step 3: What should positive positions be?

Look at an even position $i$. It is positive.

If $i$ has both neighbors, then the length-$3$ subarray around it is:

$$[-1, a_i, -1].$$

Its sum must be positive:

$$-1+a_i-1>0.$$

So:

$$a_i>2.$$

Since $a_i$ is an integer,

$$a_i\ge 3.$$

That means every “middle” positive element must be at least $3$.

What about the last element if $n$ is even? It has only one negative neighbor, so length-$2$ would only require it to be at least $2$. But lexicographic order matters earlier first: every earlier even position with two neighbors already needs to be $3$. For $n=2$, the answer is just $[-1,2]$. For larger even $n$, we should check whether the final positive can be $2$.

Example ending with $\dots,-1,2$ seems locally fine. But consider a longer suffix like:

$$[-1,3,-1,2]$$

Its sum is $3$, positive. So the last positive really can be $2$ when it is the final element.

So the optimal pattern is:

• odd positions: $-1$;
• even positions: $3$;
• except when $n$ is even, the final position can be $2$.

That gives:

$$[-1,3,-1,3,-1,3,\ldots]$$

but with the last value changed to $2$ if the array ends on a positive position.

For example:

• $n=2$: $[-1,2]$
• $n=3$: $[-1,3,-1]$
• $n=4$: $[-1,3,-1,2]$
• $n=5$: $[-1,3,-1,3,-1]$

Step 4: Why every subarray sum is positive

We need prove this construction works for all subarrays of length at least $2$.

The array consists of alternating $-1$ and positive values, where every positive value is either $3$ or, only at the very end, $2$.

Any adjacent pair has sum:

$$-1+3=2$$

or possibly at the end:

$$-1+2=1.$$

So every length-$2$ subarray is positive.

For longer subarrays, group the terms into adjacent pairs. Each full pair contributes positively. If there is one leftover element, it depends on the subarray length:

• leftover positive: great, it only helps;
• leftover negative $-1$: before it, there is at least one pair containing a $3$, so the total still stays positive.

A more direct way: the worst case is when a subarray starts and ends with $-1$, because that includes one more negative than positive. Then its sum looks like:

$$(-1)+3+(-1)+3+\cdots+3+(-1).$$

With $k$ positive $3$'s and $k+1$ negative $-1$'s, the sum is:

$$3k-(k+1)=2k-1.$$

Since the subarray length is at least $3$, we have $k\ge 1$, so:

$$2k-1>0.$$

If the subarray includes the final $2$ instead of a $3$, it cannot also have a negative after it, because that $2$ is the last element. Pair it with the preceding $-1$, giving contribution $1$, still positive.

So all subarrays of length at least $2$ have positive sum.

Step 5: Why it is lexicographically optimal

Now prove nobody can beat it.

• $|a_1|=1$ is forced optimal, and the sign must be negative.
• At every odd position, $|a_i|=1$ is the absolute minimum possible.
• For every even position $i<n$, the subarray $[a_{i-1},a_i,a_{i+1}]$ exists. Since odd positions are already optimally $-1$, we need:

$$-1+a_i-1>0,$$

so $a_i\ge 3$.

Thus every even position before the end must have absolute value at least $3$.

If $n$ is even, the final position only needs to satisfy:

$$-1+a_n>0,$$

so $a_n\ge 2$, and $2$ is achievable.

Therefore the lexicographically smallest absolute values are exactly:

$$[1,3,1,3,1,3,\ldots]$$

with the last value changed from $3$ to $2$ if $n$ is even.

So output:

$$a_i=\begin{cases} -1, & i \text{ odd},\\ 2, & i=n \text{ and } n \text{ is even},\\ 3, & i \text{ even otherwise}. \end{cases}$$

That is the whole trick. Tiny construction, but the last even position being $2$ is the little trap waiting to slap lazy pattern-matching code.