തുടർച്ചയായ തുടർച്ച


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

അഭിമുഖകർ‌ക്ക് പ്രിയപ്പെട്ട മറ്റൊരു വിഷയമാണ് തുടർ‌നടപടികൾ. അവരെ ട്വീക്ക് ചെയ്യുന്നത് എല്ലായ്പ്പോഴും സ്ഥാനാർത്ഥികളെ പരീക്ഷിക്കുന്നതിനുള്ള പുതിയ അവസരങ്ങൾ നൽകും. കാര്യങ്ങൾ ചിന്തിക്കാനും വിശകലനം ചെയ്യാനുമുള്ള സ്ഥാനാർത്ഥിയുടെ കഴിവ് പരിശോധിക്കാനും മികച്ചതും മികച്ചതുമായ പരിഹാരങ്ങൾ കൊണ്ടുവരാനും ഇതിന് കഴിയും. ഇന്ന്‌ ഞങ്ങൾ‌ തുടർ‌ന്നുള്ള ഒരു പ്രശ്‌നം പരിഹരിക്കുന്നു, അത് “തുടർച്ചയായി വർദ്ധിച്ചുകൊണ്ടിരിക്കുന്ന തുടർച്ചയായ അനന്തരഫലങ്ങൾ‌” ചെയ്യും.

പ്രശ്നം പ്രസ്താവന

ആദ്യം എന്താണ് പ്രശ്നം അറിയിക്കേണ്ടതെന്ന് നോക്കാം. ഞങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ ഒരു നിര നൽകിയിരിക്കുന്നു. ഈ ശ്രേണി തരംതിരിച്ചിട്ടില്ല. വർദ്ധിച്ചുകൊണ്ടിരിക്കുന്ന ഏറ്റവും വലിയ ഉപസെറ്റ് കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ഈ സംഖ്യകൾ‌ക്കിടയിൽ അവയ്‌ക്ക് ഒന്നിന്റെ വ്യത്യാസം ഉണ്ടായിരിക്കണമെന്ന് റൂൾ‌ പ്രസ്താവിക്കുന്നു.

ഉദാഹരണം

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 പരിശോധിക്കുന്നു.
  • ഹാഷ്‌മാപ്പിന് കീ ഉണ്ടെങ്കിൽ തുടർന്നുള്ളതിലേക്ക് ഞങ്ങൾ ചേർക്കുന്നു
  • ഞങ്ങളുടെ സ ience കര്യത്തിനും സ്ഥലം സംഭരിക്കുന്നതിനും മുമ്പത്തെ കീ ഇല്ലാതാക്കാം
  • ഹാഷ്‌മാപ്പിന് കീ ഇല്ലെങ്കിൽ
  • നിലവിലെ ഘടകത്തിന്റെ കീയായി ഞങ്ങൾ 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

ഞങ്ങൾ ജാവയിൽ നിന്ന് സി ++ ലേക്ക് മാറുമ്പോൾ. ഞങ്ങൾ കളക്ഷൻ ഫ്രെയിംവർക്കിൽ നിന്ന് എസ്ടിഎലിലേക്ക് മാറുന്നു. അങ്ങനെ, ഞങ്ങൾ ഇതിലേക്ക് മാറുകയാണ് ക്രമീകരിക്കാത്ത മാപ്പുകൾ നിന്ന് ഹാഷ്‌മാപ്പ്. ഇപ്പോൾ മാറ്റങ്ങൾ ഞങ്ങൾക്കറിയാം, ഭാഷ മാറാൻ ഞങ്ങളെ അനുവദിക്കുക.

തുടർച്ചയായി വർദ്ധിച്ചുകൊണ്ടിരിക്കുന്ന തുടർച്ചയായ ദൈർഘ്യം കണ്ടെത്താൻ സി ++ കോഡ്

#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) ന്റെ സ്ഥല സങ്കീർണ്ണതയിലേക്ക് നയിക്കുന്നു