สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มไม่ซ้ำกัน N เราต้องหาองค์ประกอบสูงสุดในช่วงเวลา [L, R] เพื่อให้ช่วงเวลามีหนึ่งในจำนวนเต็ม N ที่กำหนดและ 1 <=L <=R <=10 5 .
ดังนั้นหากอาร์เรย์เป็นเหมือน 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
