\(A\) の要素の中で大きい方から \(N\) 個を黒に塗り、残りを白に塗ることにします。(同率の場合、黒い要素がちょうど \(N\) 個になるように適当に選んで塗ります)
もし、全ての対応する括弧が黒い要素と白い要素をペアにしていれば、スコアは、\(A\) を昇順ソートしたものを \(A'\) として、\(\displaystyle (\sum_{i = N + 1}^{2N} A'_i) - ( \sum_{i = 1}^N A'_i)\) となり、明らかに達成し得る最大値となります。

実は、以下のような処理を行うとそのような括弧列を構成することができます。

• 構築する括弧列を \(s\) とする
• スタック \(a\) (最初は空) を持つ
• \(i = 1, 2, 3, \dots, 2N\) の順に以下の処理を行う
  • もし \(a\) に \(A_i\) と違う色の要素が入っていれば、\(a\) から \(1\) つ pop し、pop した要素に対応する位置の \(S\) の文字を ( とし、\(S_i\) を ) とする
  • そうでなければ、\(A_i\) を \(a\) に push する (\(S_i\) は決定せず保留する)

スタックの性質上、同時に決まった ( と ) は対応する括弧となります。また、明らかに同時に決まった \(2\) つの括弧に対応する \(A\) の要素は異なる色です。
\(a\) に白の要素と黒の要素が同時に入っていることはないので、(白の要素と黒の要素が同数ある以上) 終了時には \(a\) は空になっています。
よって、この処理は最適なスコアを達成する括弧列 \(s\) を正しく構成することができます。