C++-এ দীর্ঘতম ক্রমবর্ধমান অনুক্রমের সংখ্যা

ধরুন আমাদের একটি পূর্ণসংখ্যার বিন্যাসবিহীন অ্যারে আছে। আমাদের দীর্ঘতম ক্রমবর্ধমান অনুক্রমের সংখ্যা খুঁজে বের করতে হবে, তাই যদি ইনপুটটি [1, 3, 5, 4, 7] এর মত হয়, তাহলে আউটপুট হবে 2, কারণ ক্রমবর্ধমান অনুক্রমগুলি [1,3,5,7] এবং [১, ৩, ৪, ৭]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=সংখ্যা অ্যারের আকার, n আকারের দুটি অ্যারে len এবং cnt তৈরি করুন এবং মান 1 দিয়ে পূরণ করুন।
• লিস :=1
• আমি 1 থেকে n
  পরিসরে
  • 0 থেকে i – 1
    পরিসরে j-এর জন্য
    • যদি nums[i]> nums[j] হয়, তারপর
      • যদি len[j] + 1> len[i], তারপর len[i] :=len[j] + 1, এবং cnt[i] :=cnt[j]
      • অন্যথায় যখন len[j] + 1 =len[j], তারপর cnt[i] :=cnt[i] + cnt[j]
    • lis :=লিস এবং লেনের সর্বোচ্চ [j]
• উত্তর :=0
• আমি 0 থেকে n – 1
  পরিসরে
  • যদি len[i] =lis, তাহলে ans :=ans + cnt[j]
• উত্তর ফেরত দিন

উদাহরণ(C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include Namespace ব্যবহার করে std;class Solution {public:int findNumberOfLIS(vector&nums) { int n =nums.size(); ভেক্টর  len(n, 1), cnt(n, 1); int lis =1; for(int i =1; i  nums[j]){ if(len[j] + 1> len[i]){ len[i] =len[j] + 1; cnt[i] =cnt[j]; } অন্যথায় যদি(len[j] + 1 ==len[i]){ cnt[i] +=cnt[j]; } } lis =max(lis, len[i]); } } int ans =0; for(int i =0; i  v ={1,3,5,4,7}; cout <<(ob.findNumberOfLIS(v));}

ইনপুট

আউটপুট

2