我们考虑如下贪心过程：先假装所有位置都是 )，每次尝试改一对 ( 并检查后缀和，如果后缀和仍然都 $\leq 0$ 那么合法，否则非法。

我们只需要证明：如果后缀和合法，并且原序列有解，那么改成 ( 仍然有解。假设这两个位置为 $i,j$，如果我们可以找到 $i< i',j< j'$ 满足 $(i',j')$ 选择了 (，那么交换匹配不劣。否则因为后续必有 )，所以只有 $i< i'< j'< j$ 的 $(i',j')$ 选择了 ( 。此时交换匹配，检查后缀。

然后你发现，此时检查后缀，和插入 $(i,j)$ 时检查后缀并无区别。仍然是合法的，因此交换仍然合法。