পাইথনে Longest Increasing Subsequence (সর্বাধিক দীর্ঘ বর্ধমান সাবসিকোয়েন্স)

মান করুন একটি আনসোর্টেড ইন্টিজার লিস্ট আছে। আমাদের সর্বাধিক দীর্ঘ বর্ধমান সাবসিকোয়েন্স বের করতে হবে। ইনপুট [10,9,2,5,3,7,101,18] হলে আউটপুট হবে ৪, কারণ বর্ধমান সাবসিকোয়েন্সটি [2,3,7,101]।

সমাধানের ধাপগুলো:

trails := ০ থেকে len(nums)-1 দৈর্ঘ্যের একটি অ্যারে, ০ দিয়ে ফিল করা
size := 0
nums-এ প্রতিটি x এর জন্য
- i := 0, j := size
- i != j যতক্ষণ
  - mid := i + (j - i) // 2
  - যদি trails[mid] < x, তবে i := mid + 1, অন্যথায় j := mid
- trails[i] := x
- size := max(i + 1, size)
size রিটার্ন করুন

নিচে ইমপ্লিমেন্টেশন দেওয়া হলো:

উদাহরণ

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)
        return size

ob1 = Solution()
print(ob1.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))

ইনপুট

[10,9,2,5,3,7,101,18]