सतत वाढणारा सततचा उपक्रम


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन Google मायक्रोसॉफ्ट
अरे डायनॅमिक प्रोग्रामिंग

सबक्वेंसेस हा मुलाखतकारांना आवडणारा आणखी एक विषय आहे. त्यांना सुमारे चिमटा काढण्यामुळे त्यांना उमेदवारांच्या चाचणीसाठी नेहमीच नवीन संधी मिळू शकतात. हे गोष्टींचा विचार करण्याची आणि विश्लेषणाची उमेदवारीची क्षमता तपासू शकते आणि सर्वोत्तम आणि चांगल्या समाधानासह येऊ शकते. आज आम्ही अनुगामी समस्येचे निराकरण करीत आहोत जी समान “दीर्घकाळ वाढणारी सातत्यपूर्ण उपक्रम” करीत आहे.

समस्या विधान

प्रथम समस्या काय व्यक्त करायची आहे ते पाहूया. आम्हाला पूर्णांकांची अ‍ॅरे दिली आहे. हे अ‍ॅरे अनसॉर्ट केलेले आहे. आमचे कार्य म्हणजे सर्वात मोठे सबसेट शोधणे जे वाढत आहे. नियमांद्वारे असे म्हटले आहे की या पूर्णांकांमधील फरक असणे आवश्यक आहे.

उदाहरण

6, 7, 2, 3, 4, 5, 9, 10

संभाव्य उपसंच

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

एक प्रतिमा एक हजार शब्द वाचतो म्हणून. तेच स्पष्टीकरण देणारी प्रतिमा पाहू. प्रतिमेमधील लाल प्रदेश पात्र उपसेट दर्शवितो.

सतत वाढणारा सततचा उपक्रम

एलआयसीएस लांबीसाठी दृष्टीकोन

ब्रुट फोर्स ते डीपी पर्यंतच्या या समस्येचे निराकरण करण्यासाठी अनेक पद्धती आहेत. जेव्हा जेव्हा असे प्रश्न विचारले जातात तेव्हा आम्ही सोपा रस्ता घेण्याकडे आणि ब्रूट फोर्सकडे लक्ष देण्याचा कल असतो. पण काळजी करू नका. मी येथे आहे सर्वोत्तम निराकरण आपल्याबरोबर पेच वाचविण्यासाठी.

  • प्रथम आपण ए तयार करतो हॅशमॅप
  • हा हॅशमॅप आपल्याकडे असलेल्या उपखंडाची लांबी संचयित करतो
  • या हॅशमॅप मधील की ही संख्या आहे.
  • मूल्य त्याच्याशी संबंधित अनुक्रमांची लांबी आहे.
  • दुसरे म्हणजे आपण अ‍ॅरेद्वारे पुनरावृत्ती करू
  • आम्ही अरर [i] -1 तपासतो.
  • जर हॅशमॅपकडे की असेल तर आम्ही अनुगामीमध्ये जोडतो
  • आमच्या सोयीसाठी आणि जागा संचयित करण्यासाठी आम्ही मागील की हटवू शकतो
  • हॅशमॅपकडे की नसल्यास
  • आम्ही सध्याच्या घटकाची की म्हणून 1 जोडतो
  • शेवटी, आम्ही सर्व लांबी कमाल शोधतो
  • अशा प्रकारे आता आमच्याकडे एलआयसीएस आहेत!

कोड

आता आम्हाला समजले आहे की ही समस्या कशी सोडवित आहे. प्रथम जावा कोडसह आमच्या कल्पना कोडवर ठेवूया.

जावा कोड सर्वात लांब वाढणारी सलग उपक्रमांची लांबी शोधण्यासाठी

import java.util.*;
public class Main
{
    public static int LICS(int[] arr)
    {
        HashMap<Integer,Integer>hash=new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(hash.containsKey(arr[i]-1))
            {
                hash.put(arr[i],hash.get(arr[i]-1)+1);
                hash.remove(arr[i]-1);
            }
            else
                hash.put(arr[i],1);
        }
        return Collections.max(hash.values());
    }
    public static void main(String args[]) 
    { 
        int arr[]={3, 10, 3, 11, 4, 5, 6, 7, 8, 12};
        System.out.println(LICS(arr));
    }
}
3, 10, 3, 11, 4, 5, 6, 7, 8, 12
6

जसे आपण जावा वरुन C ++ वर स्विच करत आहोत. आम्ही कलेक्शन फ्रेमवर्क वरुन एसटीएलमध्ये बदलत आहोत. अशाप्रकारे आपण यामध्ये बदलत आहोत अक्रमित नकाशे आरोग्यापासून हॅशमॅप. आता आपल्याला बदल माहित आहेत तर आपण भाषा बदलू या.

सी ++ कोड सर्वात लांब वाढणारी सलग उपसंक्रम लांबी शोधण्यासाठी

#include<bits/stdc++.h>
using namespace std;
int maxs(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int LICS(int arr[],int n)
{
    unordered_map<int,int>store;
    int max=-1;
    for(int i=0;i<n;i++)
    {
        if(store.find(arr[i]-1)!=store.end())
        {
            store[arr[i]]=store[arr[i]-1]+1;
        }
        else
            store[arr[i]]=1;
        max=maxs(max,store[arr[i]]);
    }
    return max;
}
int main()
{
    int a[] = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    cout << LICS(a, n); 
    return 0; 
}
3, 10, 3, 11, 4, 5, 6, 7, 8, 12
6

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

वेळ कॉम्प्लेक्सिटी = ओ (एन)

  • आम्ही संपूर्ण अ‍ॅरेमधून लूप करतो
  • आम्ही एका वेळी एका घटकाचा विचार करीत आहोत
  • म्हणून, वेळ गुंतागुंत ओ (एन) आहे

स्पेस कॉम्प्लेक्सिटी = ओ (एन)

  • आम्ही संख्या म्हणून की ठेवत आहोत
  • कळा काढतानाही, अगदी उत्तम परिस्थितीत, फक्त एक की असू शकते
  • तथापि, सर्वात वाईट प्रकरणात, आम्ही कदाचित हॅशमॅपमध्ये सर्व घटक जोडत असू
  • ज्यामुळे ओ (एन) ची अवकाश जटिलता होते