पायथन में K वेतन वृद्धि के बाद सबसे लंबे समय तक समकक्ष सबलिस्ट खोजने का कार्यक्रम

मान लीजिए हमारे पास संख्याओं की एक सूची है जिसे nums और k कहा जाता है। अब, एक ऑपरेशन पर विचार करें जहां हम किसी एक तत्व को एक बार बढ़ा सकते हैं। यदि हम अधिकतम k बार संचालन कर सकते हैं, तो हमें समान तत्वों वाली सबसे लंबी उपसूची ढूंढनी होगी।

इसलिए, यदि इनपुट अंकों की तरह है =[3, 5, 9, 6, 10, 7] k =6, तो आउटपुट 3 होगा, क्योंकि हम सबलिस्ट प्राप्त करने के लिए 9 एक बार और 6 चार बार वृद्धि कर सकते हैं [10, 10 , 10].

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

• अगर अंक खाली हैं, तो

  • वापसी 0

• wMax:=अंकों के समान आकार की एक डबल एंडेड कतार। और एक जोड़ी डालें (अंक [0], 0)

• मैं:=0, इंक:=0

• j के लिए 1 से लेकर अंकों के आकार तक, करें

  • जबकि wMax खाली नहीं है और wMax[0, 1]

    • wMax का बायां तत्व हटाएं

  • pMax :=wMax[0, 0]

  • जबकि wMax खाली नहीं है और wMax के अंतिम आइटम का पहला तत्व <=nums[j], करें

    • wMax से सही तत्व हटाएं

  • wMax के अंत में (nums[j], j) डालें

  • अगर pMax

    • inc =inc + (j - i) * (wMax[0, 0] - pMax)

  • अन्यथा,

    • inc :=inc + pMax - nums[j]

  • अगर inc> k, तो

    • inc :=inc - wMax[0, 0] - nums[i]

    • जबकि wMax खाली नहीं है और wMax[0, 1] <=i, do

      • wMax का बायां तत्व हटाएं

    • अगर wMax[0, 0] <अंक [i], तो

      • inc =inc - (अंक [i] - wMax[0, 0]) * (j - i)

    • मैं :=मैं + 1

• अंकों का वापसी आकार - i

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

उदाहरण

from collections import deque
class Solution:
   def solve(self, nums, k):
      if not nums:
         return 0
      wMax = deque([(nums[0], 0)], maxlen=len(nums))
      i = 0
      inc = 0
      for j in range(1, len(nums)):
         while wMax and wMax[0][1] < i:
            wMax.popleft()
         pMax = wMax[0][0]

         while wMax and wMax[-1][0] <= nums[j]:
            wMax.pop()
         wMax.append((nums[j], j))
         if pMax < wMax[0][0]:
            inc += (j - i) * (wMax[0][0] - pMax)
         else:
            inc += pMax - nums[j]
         if inc > k:
            inc -= wMax[0][0] - nums[i]
            while wMax and wMax[0][1] <= i:
               wMax.popleft()
            if wMax[0][0] < nums[i]:
               inc -= (nums[i] - wMax[0][0]) * (j - i)
            i += 1
      return len(nums) - i
ob = Solution()
nums = [3, 5, 9, 6, 10, 7]
k = 6
print(ob.solve(nums, k))

इनपुट

[3, 5, 9, 6, 10, 7], 6

आउटपुट

3