हमें किसी भी आकार की एक सरणी दी गई है और कार्य दी गई सरणी में उपअनुक्रम ढूंढना है जिसमें आसन्न तत्वों के बीच अंतर 0 या 1 हो।
इनपुट - int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6}
आउटपुट - आसन्न तत्वों के बीच अंतर 0 या 1 होने पर अधिकतम लंबाई उपअनुक्रम: 3
व्याख्या - सरणी में अंतर 0 या 1 वाले आसन्न तत्वों का उपअनुक्रम {2, 1} है। इसलिए, उपअनुक्रम की अधिकतम लंबाई 2 है।
इनपुट - int arr[] = { 2, 1, 7, 6, 5}
आउटपुट - आसन्न तत्वों के बीच अंतर 0 या 1 होने पर अधिकतम लंबाई उपअनुक्रम: 3
व्याख्या - सरणी में अंतर 0 या 1 वाले आसन्न तत्व {7, 6, 5} हैं। इसलिए, उपअनुक्रम की अधिकतम लंबाई 3 है।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है
- पूर्णांक प्रकार की एक सरणी इनपुट करें जिसमें सकारात्मक और नकारात्मक दोनों तत्व हो सकते हैं।
- सरणी का आकार गणना करें और आगे की कार्यक्षमता के लिए सरणी और आकार को फ़ंक्शन में पास करें।
- एक अस्थायी चर maximum लें और इसे 0 पर सेट करें और एक और अस्थायी चर i लें और इसे भी 0 पर सेट करें
- unordered_map प्रकार का एक चर un_map बनाएं
- लूप शुरू करें जब तक i size से कम है
- लूप के अंदर, len को 0 पर सेट करें और जांचें कि क्या un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1] तो len को len = un_map[arr[i]-1] पर सेट करें
- जांचें कि क्या un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]] तो len को len = un_map[arr[i]] पर सेट करें
- जांचें कि क्या un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1] तो len को len = un_map[arr[i]+1] पर सेट करें
- अब un_map[arr[i]] = len + 1 सेट करें
- जांचें कि क्या maximum, un_map[arr[i]] से कम है तो maximum को un_map[arr[i]] के साथ सेट करें
- i का मान बढ़ाएं
- maximum वापस करें
- परिणाम प्रिंट करें
कार्यक्रम उदाहरण
#include <bits/stdc++.h>
using namespace std;
// अधिकतम उपअनुक्रम गणना करें
int maximum_adj(int arr[], int size){
int maximum = 0, i = 0;
unordered_map<int, int> un_map;
while(i < size){
int len = 0;
if (un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]){
len = un_map[arr[i]-1];
}
if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]){
len = un_map[arr[i]];
}
if (un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]){
len = un_map[arr[i]+1];
}
un_map[arr[i]] = len + 1;
if (maximum < un_map[arr[i]]){
maximum = un_map[arr[i]];
}
i++;
}
return maximum;
}
int main(){
int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "आसन्न तत्वों के बीच अंतर 0 या 1 होने पर अधिकतम लंबाई उपअनुक्रम: " << maximum_adj(arr, size);
return 0;
}
आउटपुट
आसन्न तत्वों के बीच अंतर 0 या 1 होने पर अधिकतम लंबाई उपअनुक्रम: 4