ধরা যাক stacks নামক একটি স্ট্যাকের তালিকা এবং একটি পূর্ণসংখ্যা k আছে। যেকোনো স্ট্যাক থেকে মোট kটি উপাদান পপ করে সর্বোচ্চ সম্ভাব্য সমষ্টি বের করতে হবে।
উদাহরণ: stacks = [[50, -4, -15], [2], [6, 7, 8]], k = 4 হলে আউটপুট 39, কারণ প্রথম স্ট্যাক থেকে ৩টি এবং শেষ স্ট্যাক থেকে ১টি পপ করলে -15 + -4 + 50 + 8 = 39।
সমাধানের ধাপসমূহ
- rec(i, n) রিকার্সিভ ফাংশন সংজ্ঞায়িত করুন।
- বেস কেস: n == k হলে 0, n > k হলে -inf, i == len(stacks) হলে -inf।
- শেষ স্ট্যাক হলে প্রয়োজনীয় উপাদান নেইলে -inf, না হলে শেষ needed উপাদানগুলোর সমষ্টি।
- প্রতিটি স্ট্যাকে ভিন্ন সংখ্যক উপাদান পপ করে রিকার্সিভলি সর্বোচ্চ সমষ্টি বের করুন।
- মূল মেথড থেকে 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
