C++で条件arr[i+1] > arr[i]を満たす要素を最大化するアルゴリズム

はじめに

本記事では、C++を用いて「隣接する2つの要素が arr[i+1] > arr[i] を満たすように配列を並べ替え、その条件を満たすインデックスの数を最大化する」問題について解説します。

問題文

N個の整数からなる配列が与えられます。この配列の要素を並べ替えて、「次の要素が前の要素より大きい」という条件、すなわち arr[i+1] > arr[i] を満たす位置の数をできるだけ多くしてください。

入力例

入力配列が {300, 400, 400, 300} の場合、並べ替え後の配列は次のようになります。

{300, 400, 300, 400}

この並べ方では、条件 arr[i+1] > arr[i] を満たすインデックスが2つ存在するため、答えは 2 となります。

アルゴリズム

この問題は、配列内の各要素の出現頻度(重複回数)に着目することで効率的に解くことができます。

• すべての要素が互いに異なる場合： 答えは単純に n − 1 となります(n は配列の要素数)。昇順に並べ替えれば、すべての隣接ペアが条件を満たすためです。
• 重複する要素が存在する場合： 答えは n − 最大出現頻度 となります。同じ値が連続して現れる箇所では条件を満たせないため、最も多く登場する値の分だけ、達成可能なインデックス数が減少します。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
#define MAX 1000
using namespace std;
int getMaxIndices(int *arr, int n) {
   int count[MAX] = {0};
   for (int i = 0; i < n; ++i) {
      count[arr[i]]++;
   }
   int maxFrequency = 0;
   for (int i = 0; i < n; ++i) {
      if (count[arr[i]] > maxFrequency) {
         maxFrequency = count[arr[i]];
      }
   }
   return n - maxFrequency;
}
int main() {
   int arr[] = {300, 400, 300, 400};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Answer = " << getMaxIndices(arr, n) << endl;
   return 0;
}

出力結果

Answer = 2

コードのポイント

この実装では、まず各要素の出現回数をカウント配列に記録し、その中から最大頻度を求めています。最終的な答えは「要素数 n から最大頻度を引いた値」です。時間計算量は O(n)、空間計算量は O(MAX) となります。なお、要素の値の範囲が非常に大きい場合は、map<int, int> や unordered_map を使用することで同様の処理を実現できます。