C++で配列から最大周囲長の三角形を求めるアルゴリズムと実装例

問題文

非負整数の配列が与えられます。この配列から3つの要素を選び、最大の周囲長を持つ三角形を構成する組み合わせを見つけてください。

例

入力配列が {5, 1, 3, 5, 7, 4} の場合、最大周囲長は (7 + 5 + 5) = 17 となります

アルゴリズム

• 配列を降順（非増加順）にソートします。こうすることで、先頭の要素が最大値、末尾の要素が最小値になります。
• ソート後の配列で、最初の3要素が三角形を構成できるなら、それが最大周囲長の三角形となります。

この貪欲法が正しく動作する理由は、三角形不等式にあります。辺を a ≥ b ≥ c とすると、三角形が成立する条件は a < b + c です。降順にソートした配列で連続する3要素を順に調べていけば、最初にこの条件を満たした組み合わせが必ず最大周囲長になります。もし arr[i] ≥ arr[i+1] + arr[i+2] が成り立たない場合、それより小さい要素を組み合わせても三角形は作れないため、単純に次の組へ進めばよいのです。

実装例

#include <bits/stdc++.h>
using namespace std;
int getMaxPerimeter(int *arr, int n) {
   sort(arr, arr + n, greater<int>());
   int maxPerimeter = 0;
   for (int i = 0; i < n - 2; ++i) {
      if (arr[i] < arr[i + 1] + arr[i + 2]) {
         maxPerimeter = max(maxPerimeter, arr[i]
         + arr[i+1] + arr[i+2]);
         break;
      }
   }
   if (maxPerimeter) {
      return maxPerimeter;
   }
   return -1;
}
int main() {
   int arr[] = {5, 1, 3, 5, 7, 4};
   int n = sizeof(arr) / sizeof(arr[0]);
   int maxPerimeter;
   maxPerimeter = getMaxPerimeter(arr, n);
   if (maxPerimeter != -1) {
      cout << "Max perimeter = " << maxPerimeter <<
      endl;
   } else {
      cout << "Triangle formation is not possible" <<
      endl;
   }
   return 0;
}

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Max perimeter = 17

計算量

ソートに O(n log n)、その後の走査に O(n) かかるため、このアルゴリズム全体の計算量は O(n log n) です。三角形が1つも構成できない場合は、-1 を返して「三角形を作成できません」と出力します。