JavaScriptで最大周囲長となる三角形の3辺を選択する方法

問題の概要

三角形の周囲長とは、三角形の3つの辺の長さをすべて合計した値のことです。ここで扱うのは、少なくとも3つ以上の要素を含む数値配列を引数として受け取るJavaScript関数の実装です。

この関数は、配列の中から3つの辺（数値）を選び、それらを合計したときに最大の周囲長となる組み合わせを返します。ただし、単純に大きい数値を3つ選べばよいわけではなく、選んだ3辺が現実に成立する有効な三角形を形成できることを確認する必要があります。もし配列内に有効な三角形を構成できる3辺がひとつも存在しない場合は、0 を返します。

有効な三角形の条件（三角不等式）

「有効な三角形」とは、任意の2辺の和が常に残りのもう1辺より大きい三角形を指します。これは幾何学で知られる「三角不等式」に基づく条件です。例えば、3辺の長さを a・b・c とすると、次の3つの条件がすべて成り立つ必要があります。

• a + b > c
• b + c > a
• c + a > b

どれか1つでも破られていれば（例えば1辺が他の2辺の和以上になってしまう場合）、その3辺は三角形を描くことができません。

実装例

以下は、配列を昇順にソートしたうえで、大きい側から順に3辺の組み合わせを検証していくシンプルな実装です。

const arr = [1, 2, 3, 5, 6, 7, 9];

const largestPerimeter = (arr = []) => {
  // 昇順にソート（元の配列を壊さないようコピーを作成）
  const nums = [...arr].sort((a, b) => a - b);

  // 大きい方から3つずつ組み合わせを調べる
  for (let i = nums.length - 1; i >= 2; i--) {
    // 最大辺 nums[i] と、そのすぐ下の2辺で三角不等式を判定
    if (nums[i - 1] + nums[i - 2] > nums[i]) {
      // 条件を満たせば、これが最大の周囲長
      return nums[i] + nums[i - 1] + nums[i - 2];
    }
  }

  // 有効な三角形が1つも作れない場合は 0 を返す
  return 0;
};

console.log(largestPerimeter(arr));

出力結果

コンソールには次のように出力されます。

22

アルゴリズムのポイント

1. ソート： まず配列を昇順に並べ替えます。これにより「ある辺より大きい辺」の存在が明確になり、貪欲法での判定が可能になります。
2. 大きい側から走査： 配列の末尾から順に、注目している最大辺 nums[i] と、そのすぐ下の2辺 nums[i-1]・nums[i-2] の組み合わせを調べます。
3. 三角不等式の判定： nums[i-1] + nums[i-2] > nums[i] が成り立てば、その3辺で有効な三角形が形成できます。ソート済みのため、残りの2条件は自動的に満たされています。
4. 最大性の保証： 大きい数値ほど周囲長への寄与が大きいため、上から最初に見つかった有効な組み合わせが必ず最大の周囲長になります。

このアプローチの計算量はソート部分が支配的で、全体として O(n log n) です。また、元の入力配列を壊さないよう、ソート前にスプレッド構文でコピーしている点も実務上重要なポイントです。

まとめ

配列から最大周囲長の三角形を選ぶ問題は、「ソート＋貪欲法＋三角不等式チェック」という3つの要素を組み合わせることで簡潔に解けます。有効な三角形が1つも構成できないケースでは 0 を返すことを忘れないようにしましょう。