โปรแกรมหาคะแนนสูงสุดในเกมกระโดดใน Python

สมมติว่าเรามีอาร์เรย์ชื่อ nums และอีกค่าหนึ่ง k เราอยู่ที่ดัชนี 0 ในหนึ่งการเคลื่อนที่ เราสามารถกระโดดได้สูงสุด k ขั้นไปทางขวาโดยไม่ออกนอกขอบเขตของอาร์เรย์ เราต้องการไปถึงดัชนีสุดท้ายของอาร์เรย์ สำหรับการกระโดดเราจะได้คะแนน คือผลรวมของ nums[j] ทุกดัชนี 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: return 0
• ถ้า n เท่ากับ 1: return องค์ประกอบสุดท้ายของ 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, หาค่าสูงสุดในช่วง idx-k ถึง idx
  • scores[idx] := currMax + nums[idx]
• องค์ประกอบสุดท้ายของ scores := currMax + nums[-1]
• return องค์ประกอบสุดท้ายของ 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

เอาต์พุต

10