ধরুন আমাদের কাছে 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
