C++-এ সন্নিহিত এলিমেন্টের পার্থক্য ০ বা ১ হলে ম্যাক্সিমাম দৈর্ঘ্যের সাবসিকোয়েন্স

আমাদের একটি যেকোনো আকারের অ্যারে দেওয়া আছে এবং কাজ হচ্ছে সেই অ্যারেতে সাবসিকোয়েন্স খুঁজে বের করা যাতে সন্নিহিত এলিমেন্টগুলোর পার্থক্য ০ বা ১ হয়।

ইনপুট − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6}

আউটপুট − Maximum length subsequence with difference between adjacent elements as either 0 or 1 is: 3

ব্যাখ্যা − অ্যারেতে সন্নিহিত এলিমেন্ট পার্থক্য ০ বা ১ হলে সাবসিকোয়েন্স হচ্ছে {2, 1}। তাই সাবসিকোয়েন্সের ম্যাক্সিমাম দৈর্ঘ্য ২।

ইনপুট − int arr[] = { 2, 1, 7, 6, 5}

আউটপুট − Maximum length subsequence with difference between adjacent elements as either 0 or 1 is: 3

ব্যাখ্যা − অ্যারেতে সন্নিহিত এলিমেন্ট পার্থক্য ০ বা ১ হলে সাবসিকোয়েন্স হচ্ছে {7, 6, 5}। তাই সাবসিকোয়েন্সের ম্যাক্সিমাম দৈর্ঘ্য ৩।

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি নিম্নরূপ

ইনপুট একটি ইন্টিজার টাইপের অ্যারে যা পজিটিভ এবং নেগেটিভ এলিমেন্ট থাকতে পারে।
অ্যারে এর আকার ক্যালকুলেট করে অ্যারে এবং আকার ফাংশনে পাস করা হয় আরও ফাংশনালিটির জন্য।
একটি টেম্পোরারি ভেরিয়েবল maximum ০ সেট করা হয় আরেকটি টেম্পোরারি ভেরিয়েবল i ০ সেট করা হয়।
unordered_map টাইপের একটি ভেরিয়েবল un_map তৈরি করা হয়।
while লুপ শুরু করা হয় i size থেকে কম থাকার কন্ডিশন দিয়ে।
লুপের ভিতরে, len ০ সেট করা হয় এবং চেক করা হয় un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1] তবে len = un_map[arr[i]-1] সেট করা হয়।
চেক করা হয় un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]] তবে len = un_map[arr[i]]।
চেক করা হয় 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 সেট করা হয়।
চেক করা হয় maximum কম কিনা un_map[arr[i]]-এর চেয়ে তবে maximum = un_map[arr[i]]।
i-এর মান ইনক্রিমেন্ট করা হয়।
maximum রিটার্ন করা হয়।
ফলাফল প্রিন্ট করা হয়।

উদাহরণ

#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

C++-এ সন্নিহিত এলিমেন্টের পার্থক্য ০ বা ১ হলে ম্যাক্সিমাম দৈর্ঘ্যের সাবসিকোয়েন্স | সেট ২

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি নিম্নরূপ

উদাহরণ

আউটপুট