Cho mảng N số nguyên phân biệt, tìm khoảng [L,R] (1≤L≤R≤10^5) chứa đúng một số trong mảng và có độ dài lớn nhất. Ví dụ [5,10,200] → 99990 (khoảng [11,100000]).
Sắp xếp mảng, thêm 0 và 100001. Với mỗi phần tử, khoảng tối đa từ phần tử trước +1 đến phần tử sau -1. Tính độ dài lớn nhất.
Ví dụ
#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); }
Kết quả
Maximum Size is: 99990