দীর্ঘতম অনুক্রম খুঁজে বের করার জন্য প্রোগ্রাম যেখানে প্রতিটি সন্নিহিত উপাদানের মধ্যে পরম পার্থক্য পাইথনে সর্বাধিক k হয়।

ধরুন আমাদেরকে সংখ্যার একটি তালিকা এবং আরেকটি মান k দেওয়া হয়েছে। এইবার আমাদের কাজ হল দীর্ঘতম অনুক্রমের দৈর্ঘ্য খুঁজে বের করা যেখানে প্রতিটি সন্নিহিত উপাদানের মধ্যে পরম পার্থক্য সর্বাধিক k।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[5, 6, 2, 1, −6, 0, −1, k =4, তাহলে আউটপুট হবে 6।

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

একটি ফাংশন আপডেট() সংজ্ঞায়িত করুন। এটি i, x
লাগবে
i :=i + n
যখন আমি অ-শূন্য, কর
- segtree[i] :=সর্বাধিক সেগট্রি[i], x
- i :=i / 2
একটি ফাংশন ক্যোয়ারী () সংজ্ঞায়িত করুন। এটি i, j
লাগবে
উত্তর :=-অনন্ত
i :=i + n
j :=j + n + 1
যখন i
- যদি i mod 2 1 এর মত হয়, তাহলে
  - উত্তর :=সর্বাধিক উত্তর, সেগট্রি[i]
  - i :=i + 1
- যদি j mod 2 1 এর মত হয়, তাহলে
  - j :=j − 1
  - উত্তর :=সর্বাধিক উত্তর, সেগট্রি[জে]
- i :=i / 2
- j :=j / 2
উত্তর ফেরত দিন
এখন, প্রধান ফাংশনে, নিম্নলিখিতগুলি করুন -
সংখ্যা =[5, 6, 2, 1, −6, 0, −1]
k =4
n =2 থেকে পাওয়ার (লগারিদম বেস 2 এর দৈর্ঘ্য ((সংখ্যা) + 1) + 1)
segtree :=[0] * 100000
snums :=তালিকার সংখ্যা সাজান
index :=একটি সংগ্রহ করুন যেখানে x:i প্রতিটি সূচক i এবং উপাদান x এর জন্য (snums)
উত্তর :=0
প্রতিটি x সংখ্যায়, করুন
- lo :=স্নামস থেকে বাম অবস্থানে ফিরে যান, যেখানে সাজানো ক্রম বজায় রেখে (x − k) ঢোকানো যেতে পারে
- হাই :=(স্নাম থেকে বাম অবস্থান, যেখানে সাজানো ক্রম বজায় রাখার সময় (x + k) ঢোকানো যেতে পারে) −1
- গণনা :=প্রশ্ন (লো, হাই)
- আপডেট (সূচী[x], গণনা + 1)
- উত্তর :=সর্বাধিক উত্তর, গণনা + 1
উত্তর ফেরত দিন

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

উদাহরণ

import math, bisect
class Solution:
   def solve(self, nums, k):
      n = 2 ** int(math.log2(len(nums) + 1) + 1)
      segtree = [0] * 100000
      def update(i, x):
         i += n
         while i:
            segtree[i] = max(segtree[i], x)
            i //= 2
         def query(i, j):
            ans = −float("inf")
            i += n
            j += n + 1
            while i < j:
               if i % 2 == 1:
                  ans = max(ans, segtree[i])
                  i += 1
               if j % 2 == 1:
                  j −= 1
                  ans = max(ans, segtree[j])
               i //= 2
               j //= 2
            return ans
         snums = sorted(nums)
         index = {x: i for i, x in enumerate(snums)}
         ans = 0
         for x in nums:
            lo = bisect.bisect_left(snums, x − k)
            hi = bisect.bisect_right(snums, x + k) − 1
            count = query(lo, hi)
            update(index[x], count + 1)
            ans = max(ans, count + 1)
      return ans
ob = Solution()
print(ob.solve([5, 6, 2, 1, −6, 0, −1], 4))

ইনপুট

[5, 6, 2, 1, −6, 0, −1], 4