सबसे लंबे बाद का पता लगाने का कार्यक्रम जहां प्रत्येक आसन्न तत्व के बीच पूर्ण अंतर पायथन में अधिकतम k है।

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

इसलिए, यदि इनपुट nums =[5, 6, 2, 1, −6, 0, −1, k =4 जैसा है, तो आउटपुट 6 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन अपडेट () को परिभाषित करें। इसमें i, x लगेगा

• मैं :=मैं + एन

• जबकि i गैर-शून्य है, करें

  • segtree[i] :=अधिकतम segtree[i], x

  • मैं :=मैं / 2

• फ़ंक्शन क्वेरी () को परिभाषित करें। यह मैं, जम्मू ले जाएगा

• उत्तर :=−अनंतता

• मैं :=मैं + एन

• जे:=जे + एन + 1

• जबकि i

  • अगर मैं मॉड 2 1 के समान है, तो

    • उत्तर:=अधिकतम उत्तर, segtree[i]

    • मैं :=मैं + 1

  • अगर j mod 2 1 के समान है, तो

    • जे:=जे - 1

    • उत्तर:=अधिकतम उत्तर, segtree[j]

  • मैं :=मैं / 2

  • जे:=जे/2

• वापसी उत्तर

• अब, मुख्य कार्य में, निम्न कार्य करें -

• अंक =[5, 6, 2, 1, −6, 0, −1]

• कश्मीर =4

• n =2 से घात (लघुगणक आधार 2 ((अंकों की लंबाई) + 1) + 1)

• सेगट्री :=[0] * 100000

• snums :=सूची संख्या क्रमित करें

• अनुक्रमणिका :=एक संग्रह बनाएँ जहाँ x:i प्रत्येक अनुक्रमणिका के लिए i और तत्व x in (snums)

• उत्तर :=0

• अंकों में प्रत्येक x के लिए, करें

  • lo :=snums से बाईं ओर की स्थिति लौटाएं, जहां (x - k) क्रमबद्ध क्रम को बनाए रखते हुए डाला जा सकता है

  • hi :=(snums से सबसे बाईं ओर की स्थिति, जहां (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

आउटपुट

6