2つの三角形をA,Bとして、それらの3辺をそれぞれ長いほうからA1,A2,A3, B1,B2,B3とする。6辺の中で一番長い辺をA1としてよい。
入力(ai)があらかじめ長さの降順で並んでいるとする。6辺の選び方の順番を全列挙すると次のようになる:
- A1,A2,A3,B1,B2,B3
- A1,A2,B1,A3,B2,B3
- A1,A2,B1,B2,A3,B3
- A1,A2,B1,B2,B3,A3
- A1,B1,A2,A3,B2,B3
- A1,B1,A2,B2,A3,B3
- A1,B1,A2,B2,B3,A3
- A1,B1,B2,A2,A3,B3
- A1,B1,B2,A2,B3,A3
- A1,B1,B2,B3,A2,A3
これらを調べていく。三角形が成立するためには、A1<A2+A3,B1<B2+B3が成り立っていることが必要十分なので、小さいほうの4辺A2,A3,B2,B3は左に詰めても損にならない。したがって、下の列挙で−でつながった辺同士は列(ai)上で隣り合っているとしてよい。
- A1−A2−A3,B1−B2−B3
- A1−A2,B1−A3−B2−B3
- A1−A2,B1−B2−A3−B3
- A1−A2,B1−B2−B3−A3
- A1,B1−A2−A3−B2−B3
- A1,B1−A2−B2−A3−B3
- A1,B1−A2−B2−B3−A3
- A1,B1−B2−A2,−A3−B3
- A1,B1−B2−A2−B3−A3
- A1,B1−B2−B3−A2−A3
これらを3つに分類してそれぞれ最大値を計算する。
- A1−A2−A3,B1−B2−B3
これはいちばん簡単で、三角不等式を満たす連続する3辺を左から探して、見つかったらさらに3辺を探せばよい。
- A1,B1−A2−A3−B2−B3
- A1,B1−A2−B2−A3−B3
- A1,B1−A2−B2−B3−A3
- A1,B1−B2−A2,−A3−B3
- A1,B1−B2−A2−B3−A3
- A1,B1−B2−B3−A2−A3
連続する5辺のすべてについて、Bが三角不等式を満たすような選び方でA2+A3が最大になるものを検討すればよい。その選び方について、ai<A2+A3となるような最大のaiを左方から探せばよくて、これは二分探索でできる。
- A1−A2,B1−A3−B2−B3
- A1−A2,B1−B2−A3−B3
- A1−A2,B1−B2−B3−A3
やはり連続する4辺のすべてについて、Bが三角不等式を満たすような選び方でA3が最大になるものを検討すればよい……のだが、その選び方について、左方にあるai,ai+1でai−ai+1<A3を満たすものの中でai+ai+1が最大になるものを探す必要がある。これは（遅延伝搬付きの）平衡二分木に、ai−ai+1をキー、ai+ai+1を値として挿入していって、キーがA3より小さい区間の中での最大値を求めればよい。O(NlogN)。
- A1−A2−A3,B1−B2−B3
以外のパターンはすべて左に詰めることができるので、連続した6辺だけを調べればよいらしい。まったく気づかなかった。
