পাইথনে স্ট্যাকের তালিকা থেকে পপ করা k উপাদানের সর্বাধিক যোগফল খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের স্ট্যাকের একটি তালিকা এবং একটি পূর্ণসংখ্যা k আছে। স্ট্যাকের যেকোনো সংমিশ্রণ থেকে ঠিক k উপাদানগুলিকে পপ অফ করার মাধ্যমে আমাদের সর্বাধিক সম্ভাব্য যোগফল খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি স্ট্যাকের মত হয় =[[50, -4, -15],[2], [6, 7, 8]], k =4, তাহলে আউটপুট হবে 39, যেমন আমরা সবগুলো পপ অফ করতে পারি। প্রথম স্ট্যাক থেকে 3টি উপাদান এবং -15 + -4 + 50 + 8 =39 পেতে শেষ স্ট্যাকের শেষ উপাদানটি পপ করুন।

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

একটি ফাংশন rec() সংজ্ঞায়িত করুন। এটি i, n
লাগবে
n যদি k এর মত হয়, তাহলে
- রিটার্ন 0
যদি n> k, তাহলে
- রিটার্ন নেগেটিভ ইনফিনিটি
যদি আমি স্ট্যাকের সংখ্যার সমান হয়, তাহলে
- রিটার্ন নেগেটিভ ইনফিনিটি
যদি আমি স্ট্যাকের সংখ্যার সমান - 1, তাহলে
- প্রয়োজন :=k - n
- যদি প্রয়োজন হয়> স্ট্যাকের উপাদান সংখ্যা[i], তারপর
  - রিটার্ন নেগেটিভ ইনফিনিটি
- অন্যথায়,
  - স্ট্যাকের উপাদানের যোগফল [i] শেষ প্রয়োজনীয় সংখ্যক উপাদান
res :=-math.inf, su :=0
স্ট্যাকের পরিসরের আকারের sti-এর জন্য [i] - 1 থেকে 0,
1 দ্বারা হ্রাস করুন,
- su :=su + স্ট্যাকস[i, sti]
- localres :=su + rec(i + 1, n + স্ট্যাকের আকার[i] - sti)
- res :=সর্বাধিক res এবং localres
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