पायथन में ईंट हटाने वाले गेम के अधिकतम स्कोर को खोजने का प्रोग्राम

मान लीजिए अमल और बिमल एक गेम खेल रहे हैं। उनके पास एक सरणी nums है जो शीर्ष पर संख्या वाली n ईंटों को निर्धारित करती है। इस गेम में, खिलाड़ी बारी-बारी से शीर्ष से एक, दो या तीन ईंटें हटा सकते हैं, और हटाई गई ईंटों पर अंकित संख्याएं उस खिलाड़ी के स्कोर में जुड़ जाती हैं। यदि हमेशा अमल पहले शुरू करता है, तो हमें पता लगाना है कि अमल अधिकतम कितना स्कोर सुरक्षित कर सकता है।

तो, यदि इनपुट nums = [1,2,3,4,5] है, तो आउटपुट 6 होगा क्योंकि, अमल ईंट {1}, {1,2} या {1,2,3} हटा सकता है, यदि अमल पहले दो या तीन तत्वों का चयन करता है, तो बिमल सभी ले सकता है और अधिकतम स्कोर प्राप्त कर सकता है, लेकिन यदि अमल पहले 1 का चयन करता है, तो बिमल अधिकतम {2,3,4} = 9 ले सकता है और अमल 5 ले सकता है, तो अमल का कुल स्कोर 1+5 = 6 है।

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

INF := 9999
n := nums का आकार
सूची nums को उल्टा करें
temp := आकार n की एक सरणी जिसे 0 से भरा गया है
total := आकार n की एक सरणी जिसे 0 से भरा गया है
प्रत्येक इंडेक्स i, और मान val के लिए nums में, करें
- total[i] := total[i-1] + val
temp[0] := nums[0]
temp[1] := temp[0]+nums[1]
temp[2] := temp[1]+nums[2]
i को 3 से n - 1 तक की रेंज में, करें
- a := nums[i]
- b := nums[i] + nums[i-1]
- c := nums[i] + nums[i-1] + nums[i-2]
- temp[i] := a, b, c का अधिकतम
temp[n-1] लौटाएं

उदाहरण

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

INF = 99999 def solve(nums): n = len(nums) nums.reverse() temp = [0]*n total = [0]*n for i, val in enumerate(nums): total[i] = total[i-1] + val temp[0] = nums[0] temp[1] = temp[0]+nums[1] temp[2] = temp[1]+nums[2] for i in range(3, n): a = nums[i] b = nums[i] + nums[i-1] c = nums[i] + nums[i-1] + nums[i-2] temp[i] = max(a, b, c) return temp[n-1] nums = [1,2,3,4,5] print(solve(nums))

इनपुट

[1,2,3,4,5]