C++で指定されたN個の整数の1つを正確に含む最大の区間を見つけます

N個の異なる整数の配列があるとします。区間[L、R]内の最大要素を見つけて、区間に指定されたN個の整数の1つと1 <=L <=R <=10 ⁵ が含まれるようにする必要があります。 。

したがって、配列がArr =[5、10、200]のようである場合、出力は99990になります。したがって、可能な間隔はすべて[1、9]、[6、199]、および[11、100000]です。最後のものは99990のような最大整数を持っています

アイデアは単純です。間隔に含める要素を修正します。ここで、他の要素を重ねることなく、間隔を左右に拡張する方法を見ていきます。したがって、最初に配列を並べ替える必要があります。次に、固定要素の場合、前の要素と次の要素を使用して終了を決定します。コーナーケースはお世話になります。したがって、最初と最後の間隔を修正するとき。このようにして、すべての要素iについて、間隔の最大長を見つけます。

例

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int maximumSize(vector<int>& vec, int n) {
   vec.push_back(0);
   vec.push_back(100001);
   n += 2;
   sort(vec.begin(), vec.end());
   int max_value = 0;
   for (int i = 1; i < n - 1; i++) {
      int Left = vec[i - 1] + 1;
      int Right = vec[i + 1] - 1;
      int count = Right - Left + 1;
      max_value = max(max_value, count);
   }
   return max_value;
}
int main() {
   vector<int> v;
   v.push_back(200);
   v.push_back(10);
   v.push_back(5);
   int n = v.size();
   cout << "Maximum Size is: " << maximumSize(v, n);
}

出力

Maximum Size is: 99990