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