C++で比較演算子を使わずに配列の最大値を求める方法

この問題では、正の整数からなるサイズ n の配列 arr[] が与えられます。求めたいのは、関係演算子（< や > などの比較演算子）を使用せずに、配列内の最大値を見つけることです。

問題の例

入力: arr[] = {5, 1, 6, 7, 8, 2}

出力: 8

解法のアプローチ

比較演算子を使わずに値の大小を比べるには、「繰り返し減算」を利用します。2つの値を同時に1ずつ減らしていき、どちらか一方でも0より大きい間は処理を続けます。最後まで残った数が大きい方の値というわけです。

具体的には、while (x || y) というループの中で x と y をそれぞれ1ずつ減算し、ループが回った回数 c をカウントします。どちらか一方が0でない限りループは継続するため、ループ回数 c は自然と max(x, y) と一致します。

この仕組みを使い、まず配列の最初の2つの要素のうち大きい方を求め、次にその結果と残りの要素を順番に比較していきます。これを配列全体に対して繰り返すことで、すべての要素の中の最大値を求めることができます。

解法の実装例

#include <iostream>
using namespace std;

// 関係演算子を使わずに2つの値の最大値を返す関数
int returnMax(int x, int y) {

    int c = 0;

    // どちらか一方でも0でない限りループを続ける
    while(x || y)
    {
        if(x)
            x--;
        if(y)
            y--;
        c++;
    }
    return c;
}

// 配列全体の最大値を求める関数
int findMaxEle(int A[], int N) {

    int maxVal = A[0];

    for (int i = N-1; i; i--)
        maxVal = returnMax(maxVal, A[i]);

    return maxVal;
}

int main() {

    int A[] = {5, 1, 6, 7 , 8, 2};
    int N = sizeof(A) / sizeof(A[0]);
    cout<<"The maximum element of the array is "<<findMaxEle(A, N);
    return 0;
}

出力結果

The maximum element of the array is 8

計算量について

各比較では、大きい方の値の分だけループが回るため、このアルゴリズムの時間計算量は O(n × M) となります（n は配列の要素数、M は配列内の最大値）。比較演算子を一切使わないという制約条件を満たしつつ、確実に最大値を導き出せる点がこの手法の特徴です。