ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি সাজানো তালিকা নেই। আমাদের দীর্ঘতম ক্রমবর্ধমান অনুক্রমটি খুঁজে বের করতে হবে। সুতরাং যদি ইনপুট হয় [10,9,2,5,3,7,101,18], তাহলে আউটপুট হবে 4, কারণ ক্রমবর্ধমান অনুসূচী [2,3,7,101]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- trail :=দৈর্ঘ্য 0 থেকে সংখ্যা - 1 এর দৈর্ঘ্যের একটি অ্যারে, এবং এটি 0 দিয়ে পূরণ করুন
- আকার :=0
- সংখ্যায় x এর জন্য
- i :=0, j :=আকার
- যখন আমি j
- নই
- মধ্য :=i + (j - i) / 2
- যদি ট্রেইল[মধ্য]
- পথ[i] :=x
- আকার :=সর্বোচ্চ i + 1 এবং আকার
- রিটার্ন সাইজ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution(object): def lengthOfLIS(self, nums): tails =[0 for i in range(len(nums))] size = 0 for x in nums: i=0 j=size while i!=j: mid = i + (j-i)//2 if tails[mid]< x: i= mid+1 else: j = mid tails[i] = x size = max(i+1,size) #print(tails) return size ob1 = Solution() print(ob1.lengthOfLIS([10,9,2,5,3,7,101,18]))
ইনপুট
[10,9,2,5,3,7,101,18]
আউটপুট
4