পাইথনে প্রদত্ত শর্ত সহ দীর্ঘতম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা আছে, আমাদেরকে দীর্ঘতম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করতে হবে যেখানে 2 * সর্বনিম্ন সাবলিস্ট> সর্বোচ্চ সাবলিস্ট।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[10, 2, 6, 6, 4, 4], তাহলে আউটপুট 4 হবে, কারণ সাবলিস্ট [6, 6, 4,4] হল সবচেয়ে দীর্ঘতম সাবলিস্ট যা মানদণ্ড ধরে রাখে 2 * 4> 6 হিসাবে।

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

• ret :=0

• দুটি ডবল শেষ সারি minq এবং maxq

  সংজ্ঞায়িত করুন

• l :=0, r :=0

• যখন r <সংখ্যার আকার, করুন

  • n :=সংখ্যা[r]

  • যখন minq এবং n

    • minq

      থেকে শেষ উপাদান মুছুন

  • minq এর শেষে r সন্নিবেশ করুন

  • যখন maxq এবং n> nums [maxq এর শেষ উপাদান], করবেন

    • maxq

      থেকে শেষ উপাদান মুছুন

  • maxq

    এর শেষে r সন্নিবেশ করান

  • r :=r + 1

  • যখন l

    • যদি minq[0] l এর মত হয়, তাহলে

      • minq এর প্রথম উপাদান মুছুন

    • যদি maxq[0] l এর মত হয়, তাহলে

      • maxq

        এর প্রথম উপাদান মুছুন

    • l :=l + 1

  • ret :=ret এর সর্বোচ্চ এবং (r - l)

• রিটার্ন রিটার্ন

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

উদাহরণ

class Solution:
   def solve(self, nums):
      from collections import deque
      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
ob = Solution()
nums = [10, 2, 6, 6, 4, 4]
print(ob.solve(nums))

ইনপুট

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

আউটপুট

4