在C ++中找到恰好包含给定N个整数之一的最大间隔

假设我们有N个不同整数的数组。我们必须在间隔[L，R]中找到max元素，以使该间隔恰好包含给定的N个整数之一，并且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