সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ সর্বোচ্চ দৈর্ঘ্যের অনুচ্ছেদ 0 বা 1 হয়  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় সিসকো এক্সপিডিয়া Qualtrics এসএপি ল্যাব তেরদাটা
বিন্যাস ডায়নামিক প্রোগ্রামিং

সমস্যা বিবৃতি  

আপনি একটি দেওয়া হয় পূর্ণসংখ্যা বিন্যাস। সমস্যা "সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ সর্বাধিক দৈর্ঘ্যের অনুপাতটি 0 বা 1 হিসাবে হয়" সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ সর্বাধিক অনুপাতের দৈর্ঘ্যটি 0 বা 1 বাদে আর কোনও হওয়া উচিত না তা জানতে চেয়েছিল।

উদাহরণ  

arr[] = {1, 4, 5, 2, 6, 5, 4, 8}
5

ব্যাখ্যা

উপসূতি = 4, 5, 6, 5, 4

arr[] = {1, -3, -2, 0, -1, -2, -3, -4}
6

ব্যাখ্যা

উপসত্তা = -3, -2, -1, -2, -3, -4

সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ 0 বা 1 হিসাবে সর্বাধিক দৈর্ঘ্যের অনুচ্ছেদটি সন্ধান করতে অ্যালগরিদম  

1. Declare a Map.
2. Set maxValue to 0.
3. Traverse the array starting from i=0 to while i<n (length of the array).
  1. Initialize a variable temp to 0.
  2. Check if Map contains the key as arr[i-1],
    1. If true, then get the value of arr[i-1] and store it to temp.
  3. Check if Map contains the key as arr[i],
    1. If true, then find the greater between the temp and the value of arr[i] in the map, and store it to temp.
  4. Check if Map contains the key as arr[i+1],
    1. If true, then find the greater between the temp and the value of arr[i+1] in the map, and store it to temp.
  5. Check if the temp is greater than maxValue,
    1. If true then store the value of temp to maxValue.
  6. And put the arr[i] as a key and temp as a value into the map.
4. Return maxValue.

ব্যাখ্যা

আরো দেখুন
কোনও অ্যারে স্ট্যাক বাছাইযোগ্য কিনা তা পরীক্ষা করুন

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

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

উদাহরণ

অ্যার [] = {1, 4, 5, 2, 6, 5, 4, 8}

প্রথম কাজটি আমরা হ'ল একটি ড মানচিত্র কারণ আমরা আলোচনা করা অ্যালগরিদম অনুযায়ী একটি অ্যারে উপাদান এবং মান টেম্প সংরক্ষণ করতে যাচ্ছি। সর্বাধিক মানটির মান 0 এ সেট করুন। আমরা এই পরিবর্তনশীলটি ফিরিয়ে আনতে চলেছি। যে পরিবর্তনশীল কি আমাদের উত্তর হবে। আমরা অ্যারেটিকে অতিক্রম করব এবং এটি অ্যারের দৈর্ঘ্যে পৌঁছে দেব। প্রতিবার আমরা i এর নতুন মান দিয়ে অ্যারেটি অতিক্রম করি, আমরা 0 তে একটি মান টেম্পার্টেশিয়াল করি।

i = 0, আরআর [i] = 1, অস্থায়ী = 0, সর্বোচ্চ মান = 0 মানচিত্র = {

কোন শর্ত পূরণ করতে চলেছে তা পরীক্ষা করুন। এক্ষেত্রে কোনও শর্ত নেই। সুতরাং এটি অস্থায়ী ++ করে এবং টেম্পটি সর্বোচ্চমাত্রার চেয়ে বড় কিনা তা পরীক্ষা করে। যদি সত্য হয় তবে টেম্পটিকে ম্যাক্সভ্যালুতে সঞ্চয় করুন এবং মান এবং মানচিত্রটি মানচিত্রে sertোকান।

i = 1, আরআর [i] = 4, অস্থায়ী = 0, সর্বোচ্চ মান = 1 ue

মানচিত্র = {1,1}

উপরের শর্ত হিসাবে একই, আমরা মানচিত্র স্রেফ সন্নিবেশ করান

i = 2, আরআর [i] = 5, অস্থায়ী = 0, সর্বোচ্চ মান = 1 ue

আরো দেখুন
প্রদত্ত রেঞ্জগুলিতে এমনকি বা বিজোড় সংখ্যার সম্ভাবনা সম্পর্কিত প্রশ্নগুলি

মানচিত্র = {1: 1, 4: 1}

এবার আমরা প্রথম শর্তটি সঠিকভাবে আবিষ্কার করেছি যে মানচিত্রে আরার [i] -1 রয়েছে যা 4 হয় So সুতরাং এটি 1টিকে একটি অস্থায়ী হিসাবে নেয় এবং টেম্প ++ করে। তারপরে সর্বাধিক 2 টিতে পরিবর্তন করুন এবং এআর [i] ]োকান এবং এতে টেম্পোর করুন।

এবং কেবল এইরকম, আমরা শর্তগুলি পরীক্ষা করে দেখাব এবং মানগুলিকে সাময়িকভাবে গ্রহণ করব। এটি একটি মানচিত্রে সন্নিবেশ করা চালিয়ে যান, শেষ অবধি, আমরা আমাদের আউটপুট হিসাবে ম্যাক্সভ্যালুতে মান পাই।

সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ সর্বোচ্চ দৈর্ঘ্যের অনুচ্ছেদ 0 বা 1 হয়

কোড  

সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য সহ 0 বা 1 হিসাবে সর্বাধিক দৈর্ঘ্যের অনুচ্ছেদটি সন্ধান করতে সি ++ কোড

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumLenSubsequence(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int maxValue = 0;
    for (int i=0; i<n; i++)
    {
        int temp = 0;
        if (MAP.find(arr[i]-1) != MAP.end() && temp < MAP[arr[i]-1])
            temp = MAP[arr[i]-1];

        if (MAP.find(arr[i]) != MAP.end() && temp < MAP[arr[i]])
            temp = MAP[arr[i]];

        if (MAP.find(arr[i]+1) != MAP.end() && temp < MAP[arr[i]+1])
            temp = MAP[arr[i]+1];

        MAP[arr[i]] = temp + 1;

        if (maxValue < MAP[arr[i]])
            maxValue = MAP[arr[i]];
    }
    return maxValue;
}
int main()
{
    int arr[] = {1, 4, 5, 2, 6, 5, 4, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumLenSubsequence(arr, n);
    return 0;
}
5

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

import java.util.HashMap;

class subsequenceLength
{
    public static int getMaximumLenSubsequence(int[] arr)
    {
        int maxValue = 0;
        HashMap<Integer, Integer> MAP = new HashMap<>();
        for (int i = 0; i < arr.length; i++)
        {
            int temp = 0;
            if (MAP.containsKey(arr[i] - 1))
            {
                temp = MAP.get(arr[i] - 1);
            }

            if (MAP.containsKey(arr[i]))
            {
                temp = Math.max(temp, MAP.get(arr[i]));
            }

            if (MAP.containsKey(arr[i] + 1))
            {
                temp = Math.max(temp, MAP.get(arr[i] + 1));
            }
            temp++;
            if (temp > maxValue)
            {
                maxValue = temp;
            }
            MAP.put(arr[i], temp);
        }
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 5, 2, 6, 5, 4, 8};
        System.out.println(getMaximumLenSubsequence(arr));
    }
}
5

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

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। আমরা অ্যারেতে সমস্ত উপাদানগুলিতে কেবল পেরেছি। যেহেতু আমরা হ্যাশম্যাপ ব্যবহার করেছি আমরা লিনিয়ার সময় জটিলতায় এটি করতে সক্ষম হয়েছি।

আরো দেখুন
কুলডাউন লেটকোড সলিউশন সহ স্টক কেনা বেচার সেরা সময়

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

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু আমরা মানচিত্রে উপাদানগুলির সাথে সম্পর্কিত ডেটা সংরক্ষণ করছি তাই স্থান জটিলতাও লিনিয়ার।