結論としては、次の操作によりACを得ることができます。

• 棒の長さをソートしたときに連続する \(3\) 本の棒の組を全て調べる

以下で理由を説明します。

最長の棒が \(k\) 番目の棒である場合を考えます。このとき、 \(k\) 以外で長さが \(L_k\) 以下のものを \(2\) 本選び、その長さの和が \(L_k\) を超えるようにすることができれば、三角形を作ることができます。よって、長さ \(L_k\) 以下の棒のうち、 \(k\) を除いて長い方から \(2\) 本の棒を取って、この \(2\) 本の棒の和が \(L_k\) を超えるかを調べれば良いです。

三角形を作ることができる場合に、その最大を求めることを考えます。最長の辺を \(L_k\) として固定し、これを底辺とします。このとき、底辺の両端は必ず鋭角になります。この状況の下で、最長の辺以外のうち片方のみを（ \(L_k\) を超えない範囲で）長いものに取り換えると、底辺に対する高さは必ず増えることがわかります。よって、先ほどと同様に、長さ \(L_k\) 以下の棒のうち、 \(k\) を除いて長い方から \(2\) 本の棒を取ったときが（三角形を作ることができるならば）最大の面積となります。

棒の長さをソートしたとき、「 \(k\) 番目の棒と、 \(k\) を除いて長い方から \(2\) 本の棒を取る」という操作は、ソートした配列上で隣り合う \(3\) 本の棒を選ぶという操作として実現できます。以上より、棒の長さをソートして、連続する \(3\) 本の棒を全通り試し、その中で面積が最大になるもの（三角形になるものがなければ -1 ）が答えとなります。 \(3\) 辺がわかったときの三角形の面積の \(2\) 乗は、ヘロンの公式によって求めることができます。計算量は各ケースに対して \(O(N\log N)\) です。