সুসংগত উপাদানগুলির সাথে বৃহত্তম সুবরের দৈর্ঘ্য  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ব্লুমবার্গ সিসকো ক্যারাট মনোোটাইপ সমাধান Paytm Payu পাবলিকিস সেপিয়েন্ট এসএপি ল্যাব
বিন্যাস কাটা

"সংমিশ্রিত উপাদানগুলির সাথে বৃহত্তম সুব্রেরির দৈর্ঘ্য" সমস্যাটি আপনাকে জানায় যে একটি দেওয়া হয়েছে পূর্ণসংখ্যা বিন্যাস। সমস্যার বিবৃতিটি দীর্ঘতম সুসংগত সাব-অ্যারের দৈর্ঘ্য নির্ধারণ করতে জিজ্ঞাসা করে যাগুলির উপাদানগুলি ক্রমিকভাবে সাজানো যেতে পারে (ক্রমাগত, হয় আরোহী বা উতরাই)। অ্যারেতে সংখ্যাগুলি একাধিকবার ঘটতে পারে।

উদাহরণ  

সুসংগত উপাদানগুলির সাথে বৃহত্তম সুবরের দৈর্ঘ্যপিন

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

ব্যাখ্যা

0 তম সূচক থেকে তৃতীয় সূচকে শুরু হওয়া সংখ্যায় 3, 10, 12, 13 সংখ্যা রয়েছে যা 11, 10, 11, 12 পদ্ধতিতে সাজানো যেতে পারে যার দৈর্ঘ্য 13 হয়ে যায়।

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

ব্যাখ্যা

১ ম সূচী থেকে তৃতীয় সূচক পর্যন্ত শুরু হওয়া সংখ্যায় 1, 3, 1 নম্বর রয়েছে যা দৈর্ঘ্য 3 হয়ে যায় এমন 2, 1, 2 পদ্ধতিতে সাজানো যেতে পারে।

অ্যালগরিদম  

  1. সেট সর্বোচ্চ দৈর্ঘ্য 1 তে
  2. একটি লুপ খুলুন, i = 0, যখন আমি <l -1,
    1. ঘোষণা করুন ক সেট এবং সেটে আরআর [i] যুক্ত করুন।
    2. এর মান নির্ধারণ করুন ম্যাক্সলেন এবং মিনল to arr [i]।
    3. J = i + 1 থেকে শুরু করে একটি লুপ খুলুন, যখন জ <এল,
      1. সেটের আরার মান [জে] আছে কিনা তা পরীক্ষা করুন,
        1. যদি সত্য হয়, বিরতি।
        2. অন্য,
          1. আর্ট [j] সেট এ যুক্ত করুন।
          2. মিলেন এবং আরার [জে] এর মধ্যে সর্বনিম্ন সন্ধান করুন এবং এটি মিলনে সংরক্ষণ করুন।
          3. ম্যাক্সলেন এবং অ্যার [জে] এর মধ্যে সর্বাধিক সন্ধান করুন এবং এটিকে ম্যাক্লেলেনে সংরক্ষণ করুন।
          4. সর্বোচ্চ-মিনিট = = জ - i পরীক্ষা করুন -
            1. যদি সত্য হয় তবে সর্বোচ্চ দৈর্ঘ্য এবং সর্বাধিক-মিলনে +1 এর মধ্যে সর্বাধিক সন্ধান করুন এবং এটিকে সর্বোচ্চ দৈর্ঘ্যে সংরক্ষণ করুন।
  3. সর্বোচ্চতম দৈর্ঘ্য প্রদান করুন।
আরো দেখুন
চারটি বাছাই করা অ্যারে থেকে চতুর্ভুজ গণনা করুন যার যোগফল প্রদত্ত মানের x এর সমান

ব্যাখ্যা

আমাদের একটি প্রশ্ন দেওয়া হয়েছে যা দীর্ঘতম সুসংগত সাব-অ্যারের দৈর্ঘ্য সন্ধান করতে জিজ্ঞাসা করে যার কয়েকটি সংখ্যা রয়েছে যা ক্রম অনুসারে সাজানো যেতে পারে। একটি কেস দেওয়া যেতে পারে যে প্রদত্ত অ্যারেতে নকল সংখ্যা রয়েছে। আমাদের সেই মামলাটিও পরিচালনা করা দরকার। সমাধান পেতে, আমরা একটি ব্যবহার করা হবে সেট এবং একটি নেস্টেড লুপ যা সদৃশ উপাদানগুলির যত্ন নেবে।

আসুন একটি উদাহরণ বিবেচনা করুন:

উদাহরণ

অ্যার [] = {10, 12, 13, 11, 8, 10

আমরা একটি লুপ খোলার পরে একটি সেট ব্যবহার করব এবং একবারে একটি করে সংখ্যা যুক্ত করব এবং ম্যাক্সলেন এবং মিনলেনের মান সেট করব [i]। তারপরে বর্তমান উপাদানটির আগে একটি উপাদান থেকে শুরু করে নেস্টেড লুপটি খুলুন, কারণ আমরা ইতিমধ্যে বর্তমান উপাদানটিকে সেটে প্রবেশ করিয়েছি। সেটে আরার [জে] এর মান রয়েছে কিনা তা পরীক্ষা করুন, যদি উপাদান পাওয়া যায়, তবে বিরতি দিন। অন্যথায় আরে [জে] এর মান সেট এ সন্নিবেশ করান এবং ম্যাক্সলেন এবং আরারের মধ্যে সর্বাধিক সন্ধান করুন [জে], এবং ন্যূনতম মিনলেন এবং এরি [জে] এর মধ্যে এবং যথাক্রমে ম্যাক্লেলেন এবং মিন্লেনে সংরক্ষণ করুন। ম্যাক্সেলেন-মিনিট জিয়ার সমান কিনা তা পরীক্ষা করে দেখুন, তারপরে সর্বোচ্চ দৈর্ঘ্যের মান আপডেট করুন।

সর্বোচ্চ দৈর্ঘ্য = 1।

i = 0, মাইসেট = {10}, মিনলেন = 10, ম্যাক্সেলেন = 10

j = i + 1 = 1, মাইসেটে যদি 12 টি থাকে তবে এটি মিথ্যা,

সুতরাং মাইসেটে 12 টি সন্নিবেশ করুন এবং সর্বাধিক 12 এবং 10 এবং সর্বনিম্ন সন্ধান করুন এবং 12 টি ম্যাক্লেলেন এবং 10 মিনলে সংরক্ষণ করুন এবং পরীক্ষা করুন যে ম্যাক্সেলেন-মিলেন জে - i এর সমান কিনা তবে এটি মিথ্যা।

j = 2, যদি মাইসেটের 13 টি থাকে তবে এটি মিথ্যা,

সুতরাং 13 মাইসেটে সন্নিবেশ করুন এবং সর্বাধিক 13 এবং 12 সন্ধান করুন এবং 13 কে ম্যাকলেলেনে এবং 10 কে মিনলে সংরক্ষণ করুন এবং পরীক্ষা করুন যে ম্যাক্সেলেন-মিনলেন জয়ের সমান - i মিথ্যা।

আরো দেখুন
ক্ষুদ্রতম উপাদানগুলি পুনরাবৃত্তি করে ঠিক কে টাইমস

j = 3, যদি মাইসেটের 11 টি থাকে তবে এটি মিথ্যা,

সুতরাং মাইসেটে 11 টি সন্নিবেশ করুন এবং সর্বাধিক 11 এবং 10 সন্ধান করুন এবং 13 কে ম্যাক্লেলেন এবং 10 মিনলে সংরক্ষণ করুন এবং পরীক্ষা করুন ম্যাক্সেলেন-মিনলেন জে সমান কিনা - আমি এখন সত্য কারণ 13-10 3-0 এর সমান। সুতরাং সর্বাধিক সর্বাধিক সীমাবদ্ধতা এবং ম্যাক্সেলেন-মিল্লেন + 1 সর্বাধিক (1, 13-10 + 1) সন্ধান করে সর্বাধিক আপডেট করুন এবং এটি 4 এবং 4 ম্যাক্সেলেন্থে সঞ্চিত রয়েছে এবং এটি অ্যারে অনুসরণ করতে থাকবে এবং এটি সংযুক্ত উপ-অ্যারের চেয়ে দীর্ঘ দৈর্ঘ্য না পাওয়া পর্যন্ত সেট করুন।

আউটপুট: 4

কোড  

সামঞ্জস্যপূর্ণ উপাদান সহ বৃহত্তম সুব্রেরির দৈর্ঘ্য সন্ধান করতে সি ++ কোড

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

সংলগ্ন উপাদানগুলির সাথে বৃহত্তম সাববারেটির দৈর্ঘ্য সন্ধান করতে জাভা কোড

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

জটিলতা বিশ্লেষণ  

সময় জটিলতা

চালু2) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

আরো দেখুন
যখন উপাদানগুলি একটি ব্যাপ্তিতে সীমাবদ্ধ থাকে না তখন কোনও প্রদত্ত অ্যারেতে সদৃশগুলি সন্ধান করুন

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।