पायथन में ढेर की सूची से पॉप किए गए k तत्वों की अधिकतम राशि खोजने का कार्यक्रम

मान लीजिए कि हमारे पास ढेर की एक सूची है और एक पूर्णांक k है। हमें स्टैक के किसी भी संयोजन से बिल्कुल k तत्वों को पॉप करने से प्राप्त किया जा सकने वाला अधिकतम संभव योग खोजना होगा।

इसलिए, यदि इनपुट स्टैक की तरह है =[[50, -4, -15], [2], [6, 7, 8]], k =4, तो आउटपुट 39 होगा, क्योंकि हम सभी को पॉप ऑफ कर सकते हैं -15 + -4 + 50 + 8 =39 प्राप्त करने के लिए पहले स्टैक से 3 तत्व और अंतिम स्टैक के अंतिम तत्व को पॉप करें।

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

• फ़ंक्शन rec() को परिभाषित करें। इसमें मुझे, n

  . लगेगा

• यदि n, k के समान है, तो

  • वापसी 0

• यदि n> k, तो

  • नकारात्मक अनंत लौटाएं

• अगर मैं ढेर की गिनती के समान हूं, तो

  • नकारात्मक अनंत लौटाएं

• अगर मैं स्टैक -1 की गिनती के समान हूं, तो

  • आवश्यक :=k - n

  • यदि आवश्यक हो> ढेर की तत्व गणना [i], फिर

    • नकारात्मक अनंत लौटाएं

  • अन्यथा,

    • स्टैक के तत्वों की वापसी का योग [i] तत्वों की अंतिम आवश्यक संख्या

• रेस:=-math.inf, सु:=0

• ढेर के रेंज आकार में sti के लिए[i] - 1 से 0,

  1 से घटाएं

  • सु:=सु + ढेर [i, sti]

  • स्थानीय:=सु + आरईसी (i + 1, n + ढेर का आकार [i] - sti)

  • रेस :=अधिकतम रेस और लोकल

• अधिकतम res और rec(i + 1, n)

  . लौटाएं

• मुख्य विधि से कॉल rec(0, 0)

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

उदाहरण

import math

class Solution:
   def solve(self, stacks, k):
      def rec(i, n):
         if n == k:
            return 0
         if n > k:
            return -math.inf
         if i == len(stacks):
            return -math.inf
         if i == len(stacks) - 1:
            needed = k - n
            if needed > len(stacks[i]):
               return -math.inf
            else:
               return sum(stacks[i][-needed:])
         res, su = -math.inf, 0
         for sti in range(len(stacks[i]) - 1, -1, -1):
            su += stacks[i][sti]
            localres = su + rec(i + 1, n + len(stacks[i]) - sti)
            res = max(res, localres)
         return max(res, rec(i + 1, n))

      return rec(0, 0)

ob = Solution()
stacks = [
   [50, -4, -15],
   [2],
   [6, 7, 8]
]
k = 4
print(ob.solve(stacks, k))

इनपुट

[[50, -4, -15],[2],[6, 7, 8]], 4

आउटपुट

39