I think my answer is exactly the same as <PERSON>'s, but I'm not sure if I should edit it.
Suppose the subsequence is $(l,r]$ and $b[i]$ is the balance at $i$-th position. If $i\notin (l,r]$, $b[i]$ won't change. Otherwise $(l,i]$, i.e. the first $i-l$ elements of $(l,r]$ is replaced by the last $i-l$ elements of $(l,r]$, which is $(r-i+l,r]$. Therefore, $b'[i]=b[l]+b[r]-b[r-i+l]$, where $b'$ is the balance of new sequence. Note that there's a bijection between $b'[i]$ and $b[r-i+l]$. It means $b'$ is non-negative iff:
1. $\forall i \notin (l,r], b[i]\ge 0$
2. $\forall i \in (l,r], b[l]+b[r]\ge b[i]$
Note that we can rewrite the second property as $b[l]+b[r]\ge max_{i\in(l,r]} b[i]$.
Let $L$ denote the rightmost position s.t. $b[i]\ge 0$ for all $i\le L$ and $R$ denote the leftmost position s.t. $b[i]\ge 0$ for all $i>R$. We need $l\le L$ and $r\ge R$ to satisfy the first constraint. We implicitly assume these constraints in all the following statements so we only need to care about the second constraint. We need three more observations:
* If $(l,r]$ is valid, for all $l'\le l$ we don't need to care about $(l',r']$ where $r'>r$.
* For all $r<r'$, if $b[r]\ge b[r']$, $(l,r]$ is better than $(l,r']$.
* Fix $l$. If $b[r']$ is the largest in $[R,r']$ and $(l,r']$ is invalid, $\forall r<r'$ $(l,r]$ is also invalid.
The first observation is trivial since we need the shortest subsequence. 532
The second observation is obvious since $b[l]+b[r]$ is larger, $(l,r]$ is shorter and the constraint is looser. The condition of the third observation follows the second: if $b[r']$ is not the largest, there exists a better $r$. Now let's see why $(l,r']$ is invalid: $b[l]+b[r']<max_{i\in(l,r']} b[i]$. Since $b[l]$ is non-negative and $b[r']$ is the largest, this can only happen if $b[l]+b[r']<max_{i\in(l,R-1]} b[i]$.So $\forall r<r'$, $b[l]+b[r]<max_{i\in(l,R-1]} b[i]$, which means $(l,r]$ is invalid. Now the flow is clear:
1. Maintain a monotone candidate list of $r$ based on the second observation. Also, maintain $max_{i\in(l,r]} b[i]$ for all $r$ in order to check the second constraint. Preprocessing takes $O(n)$.
2. Iterate $l$ from $L$ to $1$:
3. If the largest $r$ is invalid, the smaller candidates are also invalid according to the third observation. Skip this $l$.
4. If the largest $r$ is valid, check if the second largest candidate $r'$ is also valid. If so, discard $r$ according to observation one and check again. Otherwise, smaller candidates are also invalid so $r$ is optimal for $l$. Update the answer if $(l,r]$ is better. Although this step is a loop, it discards an element of $r$ when it repeats, so the total complexity is still $O(n)$.
Finally we solve the problem in $O(n)$. 532