【Python】配列から最大の周囲長を持つ三角形を求めるプログラムの実装方法

問題の概要

正の整数（辺の長さ）からなる配列 nums が与えられたとします。この中から3つの値を選んで三角形を作るとき、その周囲の長さ（perimeter）が最大になる組み合わせを求めます。ただし、面積がゼロより大きい三角形を1つも作れない場合は 0 を返します。

例えば、入力が [8,3,6,4,2,5] の場合、出力は 19 になります。これは、8・6・5 の3辺を選ぶことで 8 + 6 + 5 = 19 の周囲長を持つ三角形が作れるためです。

解き方のアプローチ

この問題は、次の手順で解くことができます。

• リスト nums を昇順にソートします。
• 末尾から要素を3つ取り出し、それぞれ a、b、c に代入します（a が最も大きい値になります）。
• b + c <= a の間（つまり三角形が成立しない間）、以下の処理を繰り返します。
  • nums が空になったら、三角形を作れないので 0 を返します。
  • a = b、b = c と値をずらし、c に新しく取り出した末尾の要素を代入します。
• ループを抜けたら、a + b + c を返します。

なぜこの方法が有効なのか

三角形の成立条件（三角不等式）では、最も長い辺が他の2辺の合計より短くなければなりません。ソート済みのリストで大きい方から3つ選んだときに条件を満たさないなら、それ以外の組み合わせが条件を満たすことはありません。そのため、条件を満たすまで候補を1つずつ下げていくだけで、必ず最大の周囲長が見つかります。計算量はソートに依存し、O(n log n) で効率的に処理できます。

実装例（Python）

以下のコードで実際の動作を確認できます。

def solve(nums):
    nums.sort()
    a, b, c = nums.pop(), nums.pop(), nums.pop()
    while b+c<=a:
        if not nums:
            return 0
        a, b, c = b, c, nums.pop()
    return a+b+c

nums = [8,3,6,4,2,5]
print(solve(nums))

入力

[8,3,6,4,2,5]

出力

19