0 किंवा 1 एकतर समीप घटकांमधील फरक सह अधिकतम लांबी अनुक्रम


अडचण पातळी मध्यम
वारंवार विचारले सिस्को यामध्ये गुण एसएपी लॅब तेराडाटा
अरे डायनॅमिक प्रोग्रामिंग

समस्या विधान

आपण एक दिले जाते पूर्णांक अॅरे. समीप घटकांमधील फरक असलेल्या जास्तीत जास्त लांबीचा अनुक्रम 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, कमाल मूल्य = XNUMX नकाशा = {

कोणती अट पूर्ण करणार आहे ते तपासा. या प्रकरणात, कोणतीही अट नाही. म्हणून ते टेम्प ++ करते आणि तात्पुरते मॅक्सव्हॅल्यूपेक्षा मोठे असल्यास तपासते. खरे असल्यास टेम्पला मॅक्सव्हॅल्यूमध्ये साठवा आणि व्हॅल्यू व टेम्प नकाशात घाला.

i = 1, अरे [i] = 4, तात्पुरते = 0, कमाल मूल्य = 1.

नकाशा = {1,1}

वरील स्थिती प्रमाणेच आम्ही फक्त व्हॅल्यूज नकाशामध्ये समाविष्ट करतो

i = 2, अरे [i] = 5, तात्पुरते = 0, कमाल मूल्य = 1.

नकाशा = {1: 1, 4: 1}

यावेळी आम्हाला प्रथम अट योग्य असल्याचे आढळले आहे की नकाशामध्ये एर [i] -1 आहे 4 आहे. म्हणून ते 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. अ‍ॅरे मधील सर्व घटकांवर आपण सहजपणे ट्रॅव्हर्स केले आहेत. कारण आम्ही हॅशमॅप वापरला आहे तो आम्ही रेषीय वेळ जटिलतेमध्ये करण्यास सक्षम होतो.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही नकाशामध्ये घटकांशी संबंधित डेटा संचयित करीत असल्याने, अवकाश जटिलता देखील रेषात्मक आहे.