参考了Logey大佬的题解在此进行感谢。Easy Version。Hard Version。首先把左括号看作1 11右括号看作− 1 -1−1求出前缀和数组s ss。若该括号序列合法则需要满足以下条件s i ≥ 0 ( 1 ≤ i ≤ n ) s_i \ge 0(1 \le i \le n)si​≥0(1≤i≤n)。s n 0 s_n0sn​0。条件二只需要对于原序列判断一下是否左括号数量等于右括号数量即可。我们现在只考虑条件一。结论s ss数组中可能会存在若干最小值指s ss数组中所有s i s_isi​中最小的s i s_isi​所对应的位置以这些最小值的后一位为开头进行循环位移一定可以构成合法的括号序列。且只有这样才可以构成合法的括号序列。蒟蒻感觉这个性质有点难以想到啊qwq证明若某个位置s i s_isi​为的最小值以他的后一位为开头进行循环位移后生成的新的前缀和数组中所有的数会在原来的前缀和数组的基础上减去s i s_isi​例如原来的前缀和数组为1 , 0 , − 1 , 0 , 1 , 0 1,0,-1,0,1,01,0,−1,0,1,0以位置三的后一位位置四以起点形成的新的前缀和数组将为1 , 2 , 1 , 2 , 1 , 0 1,2,1,2,1,01,2,1,2,1,0。由于s i s_isi​为最小值这样减完之后一定满足s i ≥ 0 ( 1 ≤ i ≤ n ) s_i \ge 0(1 \le i \le n)si​≥0(1≤i≤n)。如果不减最小值那么最小值的那些点减完之后一定会小于0 00。即对于一个括号序列其“美丽值”为s ss数组中最小值的数量。题目允许我们交换两个括号我们就要利用这个操作想办法使得s ss数组中的最小值的数量最大。那么我们就要想办法交换(与)这样的话会使得s ss数组区间减2 22。我们先随便找一个最小值循环位移一下使得序列合法。考虑操作结束后最小值是否会发生变化。不发生变化即要使得区间包含原最小值加2 22的数量最大且不包含原最小值和原最小值加1 11。发生变化需要最大化原最小值加1 11的数量且不包含原最小值。因为如果包含原最小值答案一定不会比原序列的答案更优。精细实现可以做到O ( n ) O(n)O(n)。