C++에서 주어진 N개의 정수 중 정확히 하나를 포함하는 가장 큰 간격 찾기

N개의 고유한 정수 배열이 있다고 가정합니다. 간격이 주어진 N개의 정수 중 정확히 하나와 1 <=L <=R <=10 ⁵ 를 포함하도록 간격 [L, R]에서 최대 요소를 찾아야 합니다. .

따라서 배열이 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