長さ \(n\) の括弧列を考え, このときの部分列で正しい括弧列の最大の長さを考える.

部分列の中で括弧の対応が取れているものは消して考えていい. そうすると残るのは ))))(((((( という感じの閉じ括弧の並び+開き括弧の並びである.

これは括弧列の ( を \(+1\), ) を \(-1\) として累積和を取ったときの最後の値を \(s\), 最小値を \(m\) とすると, \(-m\) 個の閉じ括弧の並び + \(s-m\) 個の開き括弧の並びとなる. よって, 部分列の中の正しい括弧列の最大の長さは \(n-s+2m\) となる.

\(T\) を考えたとき, \(n, s\) は固定なので, \(m\) ができるだけ大きくなるように \(S_i\) を並べればいいことが分かる. \(S_i\) の累積和の最小値を \(m_i\), 累積和の最後の値を \(s_i\) とすると, \(S_i, S_j\) を比べたときに \(\min(m_i, s_i+m_j) \gt \min(m_j, s_j+m_i)\) であれば \(S_i\) の方が先に使われる.

あとはこの比較関数にしたがってソートして最初から順に使っていき, 累積和の最小値を求めればいい.