আমাদের যেকোন আকারের একটি অ্যারে দেওয়া হয়েছে এবং কাজটি হল প্রদত্ত অ্যারেতে 0 বা 1 হিসাবে সন্নিহিত উপাদানগুলির মধ্যে পার্থক্য থাকা উপাদানগুলির সাথে পরবর্তীটি সন্ধান করা৷
ইনপুট − int arr[] ={ 2, 1, 5, 6, 3, 4, 7, 6}
আউটপুট − 0 বা 1 হিসাবে সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ সর্বাধিক দৈর্ঘ্য অনুক্রম হল:3
ব্যাখ্যা − 0 বা 1 এর মত পার্থক্য সহ একটি অ্যারেতে সন্নিহিত উপাদানগুলির পরবর্তী অংশ হল {2, 1}। অতএব, অনুগামীর সর্বোচ্চ দৈর্ঘ্য হল ২.
ইনপুট − int arr[] ={ 2, 1, 7, 6, 5}
আউটপুট − 0 বা 1 হিসাবে সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ সর্বাধিক দৈর্ঘ্য অনুক্রম হল:3
ব্যাখ্যা − 0 বা 1 এর মত পার্থক্য সহ একটি অ্যারের সংলগ্ন উপাদান হল {7, 6, 5}.. তাই, পরবর্তী দৈর্ঘ্যের সর্বাধিক দৈর্ঘ্য হল 3৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
টাইপ পূর্ণসংখ্যার একটি অ্যারে ইনপুট করুন যাতে ধনাত্মক এবং নেতিবাচক উপাদান থাকতে পারে।
-
একটি অ্যারের আকার গণনা করুন এবং আরও কার্যকারিতার জন্য ফাংশনে একটি অ্যারে এবং আকার পাস করুন৷
-
একটি অস্থায়ী পরিবর্তনশীল সর্বাধিক নিন এবং এটি 0 এ সেট করুন এবং আরেকটি অস্থায়ী পরিবর্তনশীল নিন এবং এটিকে 0 এ সেট করুন
-
একটি পরিবর্তনশীল un_map টাইপের unordered_map
তৈরি করুন -
আমি আকারের চেয়ে কম না হওয়া পর্যন্ত লুপ শুরু করুন
-
লুপের ভিতরে, লেন 0 এ সেট করুন এবং পরীক্ষা করুন un_map.find(arr[i]-1) !=un_map.end() &&len
-
পরীক্ষা করুন un_map.find(arr[i]) !=un_map.end() &&len
-
পরীক্ষা করুন un_map.find(arr[i]+1) !=un_map.end() &&len
-
এখন un_map[arr[i]] =len + 1
সেট করুন -
আন_ম্যাপ[আরআর[i]]-এর থেকে সর্বোচ্চ কম কিনা তা পরীক্ষা করুন তারপর আন_ম্যাপ[এআরআর[i]]]
দিয়ে সর্বোচ্চ সেট করুন -
i
এর মান বৃদ্ধি করুন -
সর্বোচ্চ রিটার্ন
-
ফলাফল প্রিন্ট করুন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
//calculate the maximum subsequence
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<<"Maximum length subsequence with difference between adjacent elements as either 0
or 1 are: "<< maximum_adj(arr, size);
return 0;
} আউটপুট
Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: 4
