पायथन में जंप गेम में प्राप्त अधिकतम स्कोर ज्ञात करने का प्रोग्राम

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

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

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

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

उदाहरण

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

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