পাইথনে পরপর দুটি উপাদানের পরম পার্থক্য k এর কম বা সমান এমন দীর্ঘতম উপক্রম

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

উদাহরণ: nums = [5, 6, 2, 1, -6, 0, -1], k = 4 হলে আউটপুট ৬।

সমাধানের ধাপসমূহ

সেগমেন্ট ট্রি ব্যবহার করে ডাইনামিক প্রোগ্রামিং প্রয়োগ করুন
update(i, x) ফাংশন দিয়ে সেগমেন্ট ট্রি আপডেট করুন
query(i, j) ফাংশন দিয়ে রেঞ্জ কোয়েরি করুন
nums সর্ট করে ইনডেক্স ম্যাপ তৈরি করুন
প্রতিটি x এর জন্য lo, hi নির্ণয় করে কোয়েরি করুন এবং আপডেট করুন
সর্বোচ্চ দৈর্ঘ্য ফেরত দিন

উদাহরণ কোড

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