मान लीजिए दो खिलाड़ी एक गेम खेल रहे हैं। जहां कई कैंडीज एक लाइन पर रखी हैं, और व्यक्ति 1 को nums नामक संख्याओं की एक सूची दी जाती है जो प्रत्येक कैंडी के पॉइंट मान को दर्शाती है। प्रत्येक व्यक्ति की बारी पर, वे लाइन के सामने से 1, 2, या 3 कैंडीज चुन सकते हैं, फिर उन्हें सूची से हटा दें, और उनके पॉइंट्स का योग उनके स्कोर में जुड़ जाता है। यह गेम तब समाप्त होगा जब सभी कैंडीज हटा दी जाएंगी और जिस व्यक्ति का स्कोर अधिक होगा वह विजेता होगा। हमें जांचना है कि व्यक्ति 1 यह गेम जीत सकता है या नहीं।
इसलिए, यदि इनपुट nums = [1, 1, 2, 3, 50] जैसा है, तो आउटपुट True होगा, क्योंकि व्यक्ति 1 1 कैंडी ले सकता है, फिर दूसरे खिलाड़ी को 1, 2 या 3 कैंडीज लेनी पड़ेंगी। किसी भी मामले में, व्यक्ति 1 50 मान वाली कैंडी ले सकता है।
हल करने के चरण
n := nums का आकार
table := तीन 0s वाला एक ऐरे।
i के लिए n - 1 से 0 तक, 1 से घटाते हुए, करें
profit := -infinity
sum_val := 0
j के लिए i से min(i + 3, n) तक की रेंज में, करें
sum_val := sum_val + nums[j]
profit := profit और (sum_val - table[j - i]) का अधिकतम
table को [profit, table[0], table[1]] मानों वाली सूची के रूप में सेट करें
यदि table[0] > 0 तो true लौटाएं, अन्यथा false
उदाहरण
import math
class Solution:
def solve(self, nums):
n = len(nums)
table = [0, 0, 0]
for i in range(n - 1, -1, -1):
profit = -math.inf
sum_val = 0
for j in range(i, min(i + 3, n)):
sum_val += nums[j]
profit = max(profit, sum_val - table[j - i])
table[:] = [profit, table[0], table[1]]
return table[0] > 0
ob = Solution()
nums = [1, 1, 2, 3, 50]
print(ob.solve(nums))
इनपुट
[1, 1, 2, 3, 50]
आउटपुट
True
