వరుసగా పెరుగుతున్న తరువాతి పరిణామం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ గూగుల్ మైక్రోసాఫ్ట్
అర్రే డైనమిక్ ప్రోగ్రామింగ్

ఇంటర్వ్యూ చేసేవారు ఇష్టపడే మరో అంశం తదుపరిది. వాటిని చుట్టుముట్టడం అభ్యర్థులను పరీక్షించడానికి ఎల్లప్పుడూ కొత్త అవకాశాలను ఇస్తుంది. ఇది విషయాలను ఆలోచించే మరియు విశ్లేషించే అభ్యర్థి సామర్థ్యాన్ని తనిఖీ చేస్తుంది మరియు ఉత్తమమైన మరియు సరైన పరిష్కారాలతో ముందుకు రాగలదు. ఈ రోజు మనం అదే "దీర్ఘకాలంగా పెరుగుతున్న వరుస పరిణామాలు" చేస్తున్న తదుపరి సమస్యను పరిష్కరిస్తున్నాము.

సమస్యల నివేదిక

మొదట సమస్యను తెలియజేయడానికి ఏమి చూద్దాం. మాకు పూర్ణాంకాల శ్రేణి ఇవ్వబడుతుంది. ఈ శ్రేణి క్రమబద్ధీకరించబడలేదు. పెరుగుతున్న అతిపెద్ద ఉపసమితిని కనుగొనడం మా పని. ఈ పూర్ణాంకాల మధ్య వాటి మధ్య ఒక వ్యత్యాసం ఉండాలని నియమం పేర్కొంది.

ఉదాహరణ

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

సాధ్యమయ్యే ఉపసమితులు

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

ఒక చిత్రం వెయ్యి పదాల విలువైనది. అదే వివరించే చిత్రాన్ని చూద్దాం. చిత్రంలోని ఎరుపు ప్రాంతం అర్హత కలిగిన ఉపసమితిని చూపుతుంది.

వరుసగా పెరుగుతున్న తరువాతి పరిణామం

LICS పొడవు కోసం అప్రోచ్

బ్రూట్ ఫోర్స్ నుండి డిపి వరకు ఈ సమస్యను పరిష్కరించడానికి అనేక పద్ధతులు ఉన్నాయి. ఇలాంటి ప్రశ్నలు అడిగినప్పుడల్లా మేము తేలికైన రహదారిని తీసుకొని బ్రూట్ ఫోర్స్‌ను పరిశీలిస్తాము. కానీ, చింతించకండి. ఉత్తమ పరిష్కారంతో మీకు ఇబ్బందిని కాపాడటానికి నేను ఇక్కడ ఉన్నాను.

  • మొదట, మేము ఒక సృష్టిస్తాము హాష్ మ్యాప్
  • ఈ హాష్ మ్యాప్ మన వద్ద ఉన్న తరువాతి పొడవును నిల్వ చేస్తుంది
  • ఈ హాష్ మ్యాప్‌లోని కీ సంఖ్య.
  • విలువ దానితో అనుబంధించబడిన తరువాతి పొడవు.
  • రెండవది, మేము శ్రేణి ద్వారా మళ్ళిస్తాము
  • మేము arr [i] -1 కోసం తనిఖీ చేస్తాము.
  • హాష్ మ్యాప్ కీని కలిగి ఉంటే, మేము తరువాతి దశకు జోడిస్తాము
  • మన సౌలభ్యం కోసం మరియు స్థలాన్ని నిల్వ చేయడానికి మునుపటి కీని తొలగించవచ్చు
  • హాష్ మ్యాప్ వద్ద కీ లేకపోతే
  • మేము ప్రస్తుత మూలకం యొక్క కీగా 1 ని చేర్చుతాము
  • చివరగా, మేము అన్ని పొడవు యొక్క గరిష్టాన్ని కనుగొంటాము
  • ఈ విధంగా, మనకు ఇప్పుడు LICS ఉంది!

కోడ్

ఈ సమస్యను ఎలా పరిష్కరిస్తున్నారో ఇప్పుడు మేము అర్థం చేసుకున్నాము. మొదట మన ఆలోచనలను జావా కోడ్‌తో కోడ్ చేయడానికి ఉంచండి.

పొడవైన పెరుగుతున్న వరుస తరువాతి పొడవును కనుగొనడానికి జావా కోడ్

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

మేము జావా నుండి సి ++ కి మారుతున్నాము. మేము కలెక్షన్ ఫ్రేమ్‌వర్క్ నుండి STL కి మారుతున్నాము. అందువలన, మేము దీనికి మారుతున్నాము క్రమం లేని పటాలు నుండి హాష్ మ్యాప్. ఇప్పుడు మార్పులు మనకు తెలుసు కాబట్టి భాషను మార్చండి.

పొడవైన పెరుగుతున్న వరుస తరువాతి పొడవును కనుగొనడానికి సి ++ కోడ్

#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

సంక్లిష్టత విశ్లేషణ

సమయ సంక్లిష్టత = O (N)

  • మేము మొత్తం శ్రేణి ద్వారా లూప్ చేస్తాము
  • మేము ఒక సమయంలో ఒక మూలకాన్ని పరిశీలిస్తున్నాము
  • అందువలన, సమయ సంక్లిష్టత O (N)

అంతరిక్ష సంక్లిష్టత = O (N)

  • మేము కీలను సంఖ్యలుగా ఉంచుతున్నాము
  • కీలను తీసివేయడంలో కూడా, ఉత్తమ సందర్భంలో, కేవలం ఒక కీ మాత్రమే ఉంటుంది
  • అయితే, అధ్వాన్నమైన సందర్భంలో, మేము అన్ని అంశాలను హాష్ మ్యాప్‌కు జోడించవచ్చు
  • ఇది O (N) యొక్క స్థల సంక్లిష్టతకు దారితీస్తుంది