पायथन में जंप गेम में हम अधिकतम अंक प्राप्त करने के लिए कार्यक्रम प्राप्त कर सकते हैं

मान लीजिए कि हमारे पास nums नामक एक सरणी है और दूसरा मान k है। हम सूचकांक 0 पर हैं। एक चाल में, हम सरणी की सीमाओं से बाहर गए बिना अधिकतम k चरणों में कूद सकते हैं। हम सरणी के अंतिम सूचकांक तक पहुंचना चाहते हैं। कूदने के लिए हमें स्कोर मिलता है, जो कि प्रत्येक इंडेक्स जे के लिए सभी अंकों [जे] का योग है जिसे हमने सरणी में देखा था। हमें वह अधिकतम अंक प्राप्त करना होगा जो हम प्राप्त कर सकते हैं।

इसलिए, यदि इनपुट nums =[1,-2,-5,7,-6,4] k =2 की तरह है, तो आउटपुट 10 होगा क्योंकि, हम इस क्रम में कूदते हैं [1, -2, 7, 4], तो हमें अधिकतम अंक मिलेगा, और वह है 10.

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

n :=अंकों का आकार
स्कोर:=आकार n की एक सरणी और 0 से भरा
स्कोर[0] :=nums[0]
currMax :=Scores[0]
max_pt :=0
अगर n <1, तो
- वापसी 0
यदि n 1 के समान है, तो
- अंकों का अंतिम तत्व लौटाएं
आईडीएक्स के लिए 1 से n -1 की सीमा में, करें
- यदि max_pt>=idx - k, तो
  - अगर currMax <स्कोर[idx-1] और idx> 0, तो
    - currMax :=Score[idx-1]
    - max_pt :=idx-1
- अन्यथा,
  - यदि idx - k> 0, तो
    - currMax:=Score[idx-k]
    - max_pt :=idx - k
    - पी के लिए idx-k से idx तक, do
      - यदि स्कोर[p]>=currMax, तो
        
        max_pt :=p
        
        currMax:=स्कोर[p]
- स्कोर[idx] :=currMax + nums[idx]
स्कोर का अंतिम तत्व :=currMax + nums[-1]
स्कोर का अंतिम तत्व लौटाएं

उदाहरण

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

def solve(nums, k):
   n = len(nums)
   scores = [0] * n
   scores[0] = nums[0]
   currMax = scores[0]
   max_pt = 0

   if n < 1:
      return 0
   if n == 1:
      return nums[-1]

   for idx in range(1,n):
      if max_pt >= idx - k:
         if currMax < scores[idx-1] and idx > 0:
            currMax = scores[idx-1]
            max_pt = idx-1
      else:
         if idx - k > 0:
            currMax = scores[idx-k]
            max_pt = idx - k
            for p in range(idx-k, idx):
               if scores[p] >= currMax:
                  max_pt = p
                  currMax = scores[p]
      scores[idx] = currMax + nums[idx]
   scores[-1] = currMax + nums[-1]
   return scores[-1]

nums = [1,-2,-5,7,-6,4]
k = 2
print(solve(nums, k))

इनपुट

[1,-2,-5,7,-6,4], 2