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


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক Citrix কোডনেশন ফেসবুক গুগল মাইক্রোসফট স্যামসাং Zoho
বাইনারি অনুসন্ধান ডায়নামিক প্রোগ্রামিং ডিএসএল

আমরা একটি সরবরাহ করা হয় বিন্যাস সংক্রমিকভাবে পূর্ণসংখ্যার এবং আমাদের দীর্ঘতম বর্ধমান অনুচ্ছেদটি খুঁজতে হবে।

  • পরেরটি ধারাবাহিক হওয়ার দরকার নেই
  • উত্তরোত্তর বৃদ্ধি পাবে

আসুন কয়েকটি উদাহরণ দ্বারা এটি আরও ভালভাবে বুঝতে পারি।

উদাহরণ

ইনপুট

[9, 2, 5, 3, 7, 10, 8]

আউটপুট

4

ব্যাখ্যা

দীর্ঘতম ক্রমবর্ধমান অনুচ্ছেদটি [2,3,7,10]।

পন্থা 1: নিষ্ঠুর শক্তি

এই পদ্ধতির সাথে সমস্ত সম্ভাব্য উপসাগর সন্ধান করা এবং প্রকৃতির মধ্যে যে দীর্ঘতম অনুচ্ছেদটি বাড়ছে তা সন্ধান করা জড়িত।

এখন, প্রতিবার আমরা অ্যারেতে ith পূর্ণসংখ্যার পরিদর্শন করি তখন দুটি ঘটনা ঘটতে পারে।

  • এটি হয় পরের অংশে অন্তর্ভুক্ত করা যেতে পারে অর্থাৎ এটি পূর্ববর্তী উপাদানগুলির চেয়ে বড়
  • এটি পূর্ববর্তী উপাদানের তুলনায় ছোট এবং অনুচ্ছেদে অন্তর্ভুক্ত করা যাবে না

তবে আমরা কোনও নির্দিষ্ট অবস্থানে উপাদানটি অন্তর্ভুক্ত করি বা না থাকুক না কেন সেই নির্দিষ্ট অবধি নির্দিষ্ট দৈর্ঘ্যের একটি বর্ধমান অনুপাত বিদ্যমান এবং আমরা সেই বিন্দু অবধি সর্বাধিক দৈর্ঘ্য ফিরিয়ে দিতে পারি। কোড স্নিপেট (জাভা এবং সি ++ এ) দ্বারা এটি আরও ভালভাবে বুঝতে পারি

দীর্ঘতম বর্ধমান উপবৃত্তির জন্য জাভা প্রোগ্রাম

class Solution 
{
    public int helper(int[] nums,int prev,int cur)
    {
        if(cur==nums.length)
            return 0;
        int on_include=0;
        //If the element at current index is greater than 
        //previous element we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(Math.max(on_include,on_ignore));
    }
    public int lengthOfLIS(int[] nums) 
    {
        int max=helper(nums,Integer.MIN_VALUE,0);
        return max;
    }
}

দীর্ঘতর বর্ধমান উপবৃত্তির জন্য সি ++ প্রোগ্রাম

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int helper(vector<int> nums,int prev,int cur)
    {
        if(cur==nums.size())
            return 0;
        int on_include=0;
        //If we are greater than previous length we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(max(on_include,on_ignore));
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
     int max=helper(nums,-1,0);
        return max;    
    }
};

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

সময় জটিলতা

O (n ^ 2) যেখানে N হ'ল অ্যারের আকার। এখানে আমরা দুটি লুপের জন্য চালাই যা আমাদের ও (এন * এন) সময়ের জটিলতায় নিয়ে যায়।

স্পেস জটিলতা ity

ও (1) কারণ আমরা কিছু পরিবর্তনশীল ব্যবহার করি যা আমাদের স্থির স্থান c0mplexity বাড়ে।

পন্থা 2: ডায়নামিক প্রোগ্রামিং

আসুন [9, 2, 5, 3, 7, 10, 8, 7] এর জন্য দীর্ঘতম বর্ধমান অনুচ্ছেদটি সন্ধান করুন।

  • এর পূর্ণসংখ্যার অ্যারের আকারের একটি অ্যারে তৈরি করি
  • প্রতিটি উপাদান হ'ল কমপক্ষে দৈর্ঘ্যের একটির একটি অনুবর্তন অর্থাৎ সংখ্যারাই এ জাতীয় দ্বারা অ্যারে আরম্ভ করে।
    11111111
  • প্রতিটি আইথ পজিশনের জন্য আমরা এর আগে jth পজিশনটি লক্ষ্য করি
  • যদি একটি [জে]
  • I = 2 এর জন্য আমরা i = 0 এবং i = 1 এর জন্য দেখতে চাই। অপারেশনগুলির পরে পরিবর্তিত অ্যারেটি দেখি
    11সর্বাধিক (জে + 1, i)

    (2)

    11111
  • সমস্ত তুলনার পরে চূড়ান্ত অ্যারে হিসাবে দেখা যেতে পারে:
    11223443
  • সকল সংখ্যার সর্বাধিক সন্ধান করা আমরা 4 সর্বাধিক অনুচ্ছেদের দৈর্ঘ্যটি খুঁজে বের করি Let's আসুন একটি কোডের মাধ্যমে এটি আরও ভালভাবে বুঝতে পারি।

দীর্ঘতম বর্ধমান উপবৃত্তির জন্য জাভা প্রোগ্রাম

class Solution 
{
    public int lengthOfLIS(int[] nums) 
    {
        int ans[]=new int[nums.length];
        for(int i=0;i<ans.length;i++)
            ans[i]=1;
        for(int i=1;i<nums.length;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=Math.max(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<ans.length;i++)
        {
            max=Math.max(ans[i],max);
        }
        return max;
    }
}

দীর্ঘতর বর্ধমান উপবৃত্তির জন্য সি ++ প্রোগ্রাম

class Solution 
{
public:
    int cmax(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
    int ans[nums.size()];
    int i,j;
        for(i=0;i<nums.size();i++)
            ans[i]=1;
        for(i=1;i<nums.size();i++)
        {
            for(j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=cmax(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<nums.size();i++)
        {
            max=cmax(ans[i],max);
        }
        return max; 
    }
};

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

সময় জটিলতা

উপরের সমাধানটির জটিলতা হ'ল ও (এন ^ 2)।

স্পেস জটিলতা ity

ও (এন) কারণ প্রতিটি সূচকের পরে উত্তর সংরক্ষণের জন্য আমরা একটি অ্যারে ব্যবহার করি।

তথ্যসূত্র