পাইথনে দিয়ে गये শর্তে সর্বোচ্চ দৈর্ঘ্যের সাবলিস্ট খুঁজে বের করার প্রোগ্রাম

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

যদি ইনপুট হয় nums = [10, 2, 6, 6, 4, 4], তবে আউটপুট হবে ৪, কারণ সাবলিস্ট [6, 6, 4, 4] হল শর্ত পূরণ করে কারণ 2 * 4 > 6।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

ret := 0
দুটি ডিক্যু minq এবং maxq সংজ্ঞায়িত করুন
l := 0, r := 0
যখন r < nums-এর আকার:
- n := nums[r]
- যখন minq এবং n < nums[minq[-1]]: minq.pop()
- minq.append(r)
- যখন maxq এবং n > nums[maxq[-1]]: maxq.pop()
- maxq.append(r)
- r := r + 1
- যখন l < r এবং nums[minq[0]] * 2 <= nums[maxq[0]]:
  - যদি minq[0] == l, minq.popleft()
  - যদি maxq[0] == l, maxq.popleft()
  - l := l + 1
- ret := max(ret, r - l)
ret ফেরত দিন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

উদাহরণ

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]