দীর্ঘতম ক্রমবর্ধমান ধারাবাহিক উপশক্তি


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক গুগল মাইক্রোসফট
বিন্যাস ডায়নামিক প্রোগ্রামিং

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

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

প্রথমে আমাদের সমস্যাটি প্রকাশ করতে হবে তা দেখুন। আমাদের পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়। এই অ্যারেটি বাছাই করা হয়েছে। আমাদের কাজটি সবচেয়ে বড় উপসেটটি খুঁজে বের করা যা ক্রমবর্ধমান। নিয়মটি উল্লেখ করছে যে এই পূর্ণসংখ্যার মধ্যে একটির মধ্যে পার্থক্য থাকা উচিত।

উদাহরণ

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

সম্ভাব্য সাবসেটগুলি

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

একটি চিত্র হিসাবে হাজার শব্দের মূল্য। আসুন আমরা একই চিত্রিত একটি চিত্র তাকান। চিত্রের লাল অঞ্চলটি উপযুক্ত উপসেট দেখায়।

দীর্ঘতম ক্রমবর্ধমান ধারাবাহিক উপশক্তি

LICS দৈর্ঘ্যের জন্য পদ্ধতির

ব্রুট ফোর্স থেকে ডিপি অবধি এই সমস্যা সমাধানের জন্য বেশ কয়েকটি পদ্ধতি রয়েছে। এই জাতীয় প্রশ্ন যখনই জিজ্ঞাসা করা হয় আমরা তত সহজ রাস্তাটি নিয়ে ব্রুট ফোর্সের দিকে নজর রাখি। কিন্তু চিন্তা করো না. আমি আপনাকে সেরা সমাধান সহকারে বিব্রততা বাঁচাতে এসেছি।

  • প্রথমত, আমরা একটি তৈরি হ্যাশ মানচিত্র
  • এই হ্যাশম্যাপটি আমাদের যে উপ-অনুচ্ছেদের দৈর্ঘ্য সঞ্চয় করে
  • এই হ্যাশম্যাপের কীটি হল নম্বর।
  • মান এটির সাথে সম্পর্কিত উপসর্গের দৈর্ঘ্য।
  • দ্বিতীয়ত, আমরা অ্যারের মাধ্যমে পুনরাবৃত্তি
  • আমরা আরআর [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

যেহেতু আমরা জাভা থেকে সি ++ এ স্যুইচ করছি। আমরা সংগ্রহ ফ্রেমওয়ার্ক থেকে এসটিএলে স্যুইচ করছি। সুতরাং, আমরা স্থানান্তরিত হয় অর্ডারযুক্ত মানচিত্র থেকে হ্যাশ মানচিত্র। এখন যেহেতু আমরা পরিবর্তনগুলি জানি আমরা আসুন ভাষাটি স্যুইচ করি।

দীর্ঘতম ক্রমবর্ধমান ধারাবাহিক উপসংশ দৈর্ঘ্যের সন্ধানের জন্য সি ++ কোড

#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

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

সময় জটিলতা = ও (এন)

  • আমরা পুরো অ্যারের মধ্য দিয়ে লুপ করি
  • আমরা একবারে একটি উপাদান বিবেচনা করছি
  • সুতরাং, সময়ের জটিলতা হ'ল (এন)

স্পেস জটিলতা = ও (এন)

  • আমরা সংখ্যা হিসাবে কীগুলি রাখছি
  • এমনকি কীগুলি অপসারণ করার ক্ষেত্রেও, সর্বোত্তম ক্ষেত্রে, কেবল একটি কী থাকতে পারে
  • তবে সবচেয়ে খারাপ ক্ষেত্রে, আমরা হ্যাশম্যাপে সমস্ত উপাদান যুক্ত করে শেষ করতে পারি
  • যা ও (এন) এর স্পেস জটিলতায় বাড়ে