左括号转为 $1$，右括号转为 $-1$。令 $S_i$ 为前缀和。

假设翻转了 $[l,r]$，则 $S_n - 2S_r + 2S_{l-1}=0$，即 $S_r = S_{l-1} + S_n/2$。且前缀和变为 $ \begin{cases} S_i, & 0 \le i < l \\ 2S_{l-1}-S_i, & l \le i \le r \\ S_i - S_n, & r < i \le n \end{cases} $。从上往下依次称为限制一、二、三。

我们定义从左往右或者从右往左（注意从右往左的时候括号也要翻转）的前缀和合法，当且仅当全部 $\ge 0$。那么，一个括号序列合法当且仅当两侧前缀和都合法。

分类讨论。

若两侧前缀和都合法，则可以直接 $O(n^2)$ 或 $O(n^3)$ DP 算出。

若恰有一侧前缀和不合法，不妨设是从左往右。考虑取前缀和第一次变为 $-1$ 之前的最大前缀和（显然，至少会有一个 $-1$），设为 $A$。再令 $B=S_n$。由于后一侧前缀和合法，因此 $S_n - S_i = B - S_i \le 0 \iff S_i \ge B$。因而 $B < 0$，否则该侧前缀和已经合法。从而直接覆盖了限制三。

于是我们自然是取 $A$ 作为 $S_{l-1}$ 最优，并取其后的第一个 $A+B/2$ 作为 $S_r$，且要求此部分均 $\le 2A$。考虑枚举第一个 $-1$ 的位置，则若 $A+B/2 \ge 0$，$l,r$ 都在其左侧，显然区间内也一定 $\le 2A$，右侧只需 $\ge B$。否则，需要其右侧存在一个合法的 $r$。左侧的方案数是好计算的。考虑将右侧全体前缀和减去 $B$，则要求：

• $S_i = -B-1$，$S_n=0$。
• $S_i, S_{i+1}, \dots, S_n \ge 0$。
• $S_i$ 到其后第一个 $S_r = A-B/2$ 中所有数 $\le 2A-B = 2(A-B/2)$。

枚举 $A-B/2$ DP 即可。

若两侧均不合法，取 $C=S_n$，$A$ 为第一次 $-1$ 前的最大值，$B$ 为最后一次 $C-1$ 后的最大值。显然，$\ge 0$ 的前缀和 $\ge C$ 的后缀是不交的，否则必然有其中一侧前缀和合法。反之亦然，因此这样是充要的。那么，不妨设 $A+C/2\le B$（否则可以倒过来求，但不要再次计算 $A+C/2=B$），则取 $A$ 与最后一次 $C-1$ 后的第一个 $A+C/2$ 即可。枚举第一个 $-1$ 的位置为 $i$，记 $j$ 为最后一次 $C-1$ 的位置，左侧依然是好算的，右侧同样考虑减去 $C$，则要求：

• $j$ 变为最后一次 $-1$ 的位置。
• $S_i = -C-1$，$S_n = 0$。
• $S_i$ 到 $j$ 后第一个 $S_r = A-C/2$ 中所有数 $\le 2A-C = 2(A-C/2)$。

类似地，枚举 $A-C/2$ DP 即可。

时间复杂度 $O(n^3)$。