C++で配列から4つの辺を選んで長方形の最大面積を求める方法

長方形の面積の基本

長方形の面積は、隣り合う2つの辺の長さを掛け合わせることで求められます。すべての長方形は4つの辺を持ち、向かい合う辺はそれぞれ同じ長さになります。面積を計算するには、「縦(長さ)」と「横(幅)」という2種類の辺の値が必要です。式で表すと次のようになります。

長方形の面積 = 縦 × 横

本記事では、長方形の辺となりうる値がランダムな順序で格納された整数型配列が与えられます。配列には4辺分の値がすべて含まれていますが、順序はバラバラです。ここでの課題は、配列の中から面積が最大化するように2組のペア(合計4つの辺)を選び出すことです。

入力例1

Arr[] = { 1,2,1,3,4,4,2,3,5,7 }

出力 − 配列から4つの辺を選んで作れる長方形の最大面積 − 12

説明 − 与えられた配列を降順にソートすると、次のようになります。

Arr[] = { 7,5,4,4,3,3,2,1,1 }

この中で最大となる2組のペア(合計4辺)は { (4,4), (3,3) } です。したがって、求められる最大面積は12平方単位となります。

入力例2

Arr[] = { 8,2,5,3,4,9,8,3,5,7 }

出力 − 配列から4つの辺を選んで作れる長方形の最大面積 − 40

説明 − 配列を降順にソートすると、次のようになります。

Arr[] = { 9,8,8,7,5,5,4,3,3,2 }

最大となる2組のペアは { (8,8), (5,5) } であるため、求められる最大面積は40平方単位です。

アルゴリズムの考え方

• 長方形の辺の候補となる値を格納した整数型配列(Arr[])を宣言します。
• 配列のサイズを保持する変数(n)を用意します。
• 関数 maxArea(int arr[], int n) は、長方形の最大面積を計算するためのもので、入力配列とそのサイズを引数として受け取ります。
• maxArea() の内部では、降順にソート済みの配列 arr[] を走査して見つかった、大きい方から2つの辺の値を格納するための配列 Dim[2] を宣言します。
• arr[] が降順にソートされているため、最も大きな4つの辺は必ず配列の先頭付近に存在します。先頭から走査し、同じ値のペアを探します。
• まず Dim[] を0で初期化しておきます。
• whileループでは、「j<2(dim[0] と dim[1] の両方がまだ見つかっていない)」かつ「i<n(配列の末尾に達していない)」という条件で処理を続けます。
• 同じ値のペアが見つかった場合(if(arr[i]==arr[i+1]))、その値を dim[j] に格納し、次の辺のために j をインクリメントします。
• 最後に dim[0] × dim[1] の積を結果として返します。
• 注意 − sort(arr, n) は配列を降順にソートする関数であるものとします。

C++実装例

#include <iostream>
using namespace std;
// 長方形の最大面積を求める関数
int maxArea(int arr[], int n){
    int dim[2]={0};
    int i=0,j=0;
    while( j<2 && i<n){
        if(arr[i]==arr[i+1]){
            dim[j++]=arr[i];
        }
        ++i;
    }
    return dim[0]*dim[1];
}
// ドライバー関数
int main(){
    int arr[] = { 1,8,5,1,8,2,5,3 };
    int n = 8;
    sort(arr,n); // 配列を降順にソートするものとする
    cout <<"Maximum area of rectangle by picking four sides from array:"<< maxArea(arr, n);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Maximum area of rectangle by picking four sides from array: 40

計算量と補足

このアルゴリズムの時間計算量は、ソートに O(n log n)、その後の走査に O(n) かかるため、全体として O(n log n) となります。空間計算量は結果を一時保存するための固定サイズ配列のみで、O(1) で済みます。

また、配列内に同じ値のペアが2組以上存在しない場合は、長方形を構成できないため dim[0] × dim[1] は0を返します。実際の開発では、このケースをエラーとして扱うか、呼び出し元で判定する設計にするとより堅牢なコードになります。