पायथन में सबसे लंबे सबसीक्वेंस की लंबाई ज्ञात करने का प्रोग्राम जहां आसन्न तत्वों के बीच निरपेक्ष अंतर अधिकतम k है

मान लीजिए हमें संख्याओं की एक सूची और एक मान k दिया गया है। हमें सबसे लंबे सबसीक्वेंस की लंबाई ज्ञात करनी है जहां हर आसन्न तत्व के बीच निरपेक्ष अंतर अधिकतम k हो।

उदाहरण के लिए, nums = [5,6,2,1,-6,0,-1], k=4 के लिए आउटपुट 6 होगा।

एल्गोरिदम (सेगमेंट ट्री + कोऑर्डिनेट कम्प्रेशन)

सेगमेंट ट्री फ़ंक्शन update(i, x) और query(i, j) परिभाषित करें
snums := सॉर्ट किया गया nums, index := मान से सॉर्ट किए गए सूचकांक का मैप
प्रत्येक x in nums (मूल क्रम में) के लिए:
- lo := bisect_left(snums, x-k), hi := bisect_right(snums, x+k)-1
- count := query(lo, hi)
- update(index[x], count+1)
- ans = max(ans, count+1)
ans वापस करें

उदाहरण

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