मान लीजिए हमारे पास स्टैक्स की एक सूची और एक पूर्णांक k है। हमें किसी भी संयोजन से स्टैक्स से ठीक k तत्व पॉप करके प्राप्त होने वाले अधिकतम संभव योग को ढूंढना है।
उदाहरण के लिए, यदि इनपुट stacks = [[50, -4, -15],[2],[6, 7, 8]], k = 4 है, तो आउटपुट 39 होगा, क्योंकि हम पहले स्टैक से सभी 3 तत्व और अंतिम स्टैक का अंतिम तत्व पॉप करके -15 + -4 + 50 + 8 = 39 प्राप्त कर सकते हैं।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (रिकर्सन + मेमोइज़ेशन):
rec(i, n)फ़ंक्शन परिभाषित करें जोi(वर्तमान स्टैक इंडेक्स) औरn(अब तक पॉप किए गए तत्वों की संख्या) लेता है।यदि
n == k, तो 0 लौटाएं।यदि
n > k, तो-infलौटाएं।यदि
i == len(stacks), तो-infलौटाएं।यदि
i == len(stacks) - 1(अंतिम स्टैक):needed := k - n।यदि
needed > len(stacks[i]), तो-infलौटाएं।अन्यथा,
stacks[i]के अंतिमneededतत्वों का योग लौटाएं।
res := -inf,su := 0।stiकोlen(stacks[i])-1से 0 तक घटाते हुए:su += stacks[i][sti]।localres := su + rec(i+1, n + len(stacks[i]) - sti)।res = max(res, localres)।
max(res, rec(i+1, n))लौटाएं।
उदाहरण
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
