पायथन में मूल्य सीमा की स्थिति के साथ सबसे लंबे समय तक सबलिस्ट की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है, हमें सबसे लंबी सबलिस्ट की लंबाई ज्ञात करनी होगी जहां 2 * (न्यूनतम सबलिस्ट)> (अधिकतम सबलिस्ट)।

इसलिए, यदि इनपुट nums =[10, 2, 6, 6, 4, 4] की तरह है, तो आउटपुट 4 होगा, क्योंकि सबलिस्ट [6, 6, 4, 4] सबसे लंबी सबलिस्ट है जो दिए गए को पूरा करती है। मानदंड (2*4)> 6.

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

• रिट:=0
• minq :=एक खाली डबल एंडेड कतार
• अधिकतम:=एक खाली डबल एंडेड कतार
• एल :=0
• r :=0
• जबकि r <अंकों का आकार, करें
  • n :=nums[r]
  • जबकि minq खाली नहीं है और n
  • मिनक से अंतिम तत्व हटाएं
• मिनक के अंत में r डालें
• जबकि maxq खाली नहीं है और n> nums[maxq का अंतिम तत्व], करते हैं
  • अधिकतम से अंतिम तत्व हटाएं
• अधिकतम के अंत में r डालें
• r :=r + 1
• जबकि l
• यदि minq[0] l के समान है, तो
  • मिनक से बायां आइटम
• यदि maxq[0] l के समान है, तो
  • अधिकतम का अंतिम आइटम हटाएं
• एल :=एल + 1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from collections import deque
def solve(nums):
   ret = 0
   minq, maxq = deque(), deque()
   l, r = 0, 0
   while r < len(nums):
      n = nums[r]
      while minq and n < nums[minq[-1]]:
         minq.pop()
      minq.append(r)
      while maxq and n > nums[maxq[-1]]:
         maxq.pop()
      maxq.append(r)
      r += 1
      while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
         if minq[0] == l:
            minq.popleft()
         if maxq[0] == l:
            maxq.popleft()
         l += 1
      ret = max(ret, r - l)
   return ret

nums = [10, 2, 6, 6, 4, 4]
print(solve(nums))

इनपुट

[10, 2, 6, 6, 4, 4]

आउटपुट

4